Near-optimal decentralized algorithms for network dynamic optimization

We study dynamic decision-making problems in networks under stochastic uncertainty about future payoffs. The network has a bounded degree, and each node takes a discrete decision at each period, leading to a per-period payoff that is a sum of three parts: node rewards for individual node decisions, temporal interactions between individual node decisions from the current and previous periods, and spatial interactions between decisions from pairs of neighboring nodes. The objective is to maximize the expected total payoffs over a finite horizon. We propose a decentralized algorithm whose computational requirement is linear in the graph size and planning horizon, and characterize sufficient conditions under which our decentralized algorithm achieves near optimality compared to the centralized global optimal. The class of decentralized algorithms is parameterized by locality parameter $L$. An $L$-local algorithm makes its decision at each node $v$ based on current and (simulated) future payoffs only up to $L$ periods ahead, and only in an $L$-radius neighborhood around $v$. Given any permitted error $\epsilon > 0$, with $L = O(\log(1/\epsilon))$, we show that $L$-local algorithm has an average per-node-per-period optimality loss of up to $\epsilon$ when temporal and spatial interactions are relatively small compared to the randomness in the node rewards and the graph degree.