Decentralized Online Convex Optimization in Networked Systems
Decentralized Online Convex Optimization in Networked Systems
复制标题
DOI：
--
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Yiheng Lin;Judy Gan;Guannan Qu;Yashodhan Kanoria;A. Wierman
中科院分区：
文献类型：
--
作者：
Yiheng Lin;Judy Gan;Guannan Qu;Yashodhan Kanoria;A. Wierman
我们研究了网络在线凸优化问题，其中每个智能体在每个时间步单独决定一个动作，并且智能体在有限时间内合作寻求最小化总的全局成本。全局代价由三种局部代价组成：凸节点代价、时间相互作用代价和空间相互作用代价。在每次决定他们的个人行动时，代理可以获得$r$-Hop邻域中下一个$k$个时间步长的局部成本函数的预测。我们的工作提出了一种新的在线算法-局部预测控制(LPC)，它将预测控制推广到多智能体系统。我们证明了在对抗性环境下，LPC的竞争比为$1+tide{O}(\rho_T^k)+de{O}(\rho_S^r)$，其中$_T$和$\rho_S$是$(0，1)$中的常数，它们分别随时间和空间相互作用成本的相对强度而增加。这是分散预测控制在网络在线凸优化中的第一个竞争比界。此外，我们还证明了我们的结果中对$k$和$r$的依赖是接近最优的，因为它是任意分散在线算法的竞争比的下界。
We study the problem of networked online convex optimization, where each agent individually decides on an action at every time step and agents cooperatively seek to minimize the total global cost over a finite horizon. The global cost is made up of three types of local costs: convex node costs, temporal interaction costs, and spatial interaction costs. In deciding their individual action at each time, an agent has access to predictions of local cost functions for the next $k$ time steps in an $r$-hop neighborhood. Our work proposes a novel online algorithm, Localized Predictive Control (LPC), which generalizes predictive control to multi-agent systems. We show that LPC achieves a competitive ratio of $1 + \tilde{O}(\rho_T^k) + \tilde{O}(\rho_S^r)$ in an adversarial setting, where $\rho_T$ and $\rho_S$ are constants in $(0, 1)$ that increase with the relative strength of temporal and spatial interaction costs, respectively. This is the first competitive ratio bound on decentralized predictive control for networked online convex optimization. Further, we show that the dependence on $k$ and $r$ in our results is near optimal by lower bounding the competitive ratio of any decentralized online algorithm.