Decentralized Protocols for the Optimization of Sensor Networks : Appendix
This paper is motivated by the problem of developing protocols for optimizing the dynamic behavior of networks of simple electronic components, such as a sensor networks. In such networks, protocols must balance multiple, competing criteria such as power consumption, delay, and buffer overflow. Our contribution is to propose a general approach of designing protocols based on policy gradient methods. In addition, this paper offers fundamental contributions to the policy gradient literature. The kind of protocol we propose can be viewed as extending policy gradient methods to a context involving a team of agents optimizing system behavior through asynchronous distributed computation and parsimonious local communication. Our main theoretical contribution is to show that the dynamics of our protocol approximate the solution to an ODE that follows the gradient of the performance objective. Consider a network consisting of a set of components V = {1, . . . , n}. Associated with this network is a discrete-time dynamical system with a finite state space W. Denote the state of the system at timek by w(k), for k = 0, 1, 2, . . .. There aren subsetsW1, . . . , Wn of W, each consisting of states associated with events at component i. At hekth epoch, there are n control actionsa1(k) ∈ A1, . . . , an(k) ∈ An, where eachAi is a finite set of possible actions that can be taken by component i. The actions are governed by a set of randomized policies π θ1 , . . . , π n θn , parameterized by vectors θ1 ∈ R1 , . . . , θn ∈ Rn. Eachith action process only transitions when the state w(k) transitions to an element of Wi. At the time of transition, the probability thatai(k) becomes anyai ∈ Ai is given byπ θi(ai|w(k)). We assume that (w(k), a(k)) is a Markov chain. While the system is in state w and actiona is applied, each component i receives a reward ri(w, a). The average reward received by the network is r(w, a) = 1 n ∑n i=1 ri(w, a). Given appropriate assumptions (see [5] for details), we can define the long-term average reward λ(θ) = limK→∞ 1 K E [∑K−1 k=0 r(w(k), a(k)) ] . We wish to find the parameters θ which maximizeλ(θ). We will consider a stochastic approximation iteration θi(k + 1) = θi(k) + χi(k). Here, > 0 is a constant step size and χi(k) is a noisy estimate of the gradient ∇θiλ(θ(k)) computed at component i based on the component’s historically observed states, actions, and rewards, in addition to communication with other components. Our goal is to develop an estimator χi(k) that can be used in an adaptive, asynchronous, and decentralized context, and to establish the convergence of the resulting stochastic approximation scheme.