论文标题
网络系统中的分散在线凸优化
Decentralized Online Convex Optimization in Networked Systems
论文作者
论文摘要
我们研究了网络在线凸优化的问题，每个代理在每个时间步骤中都会单独决定采取行动，并且代理商合作地试图最大程度地减少有限视野的全球总成本。全球成本由三种当地成本组成：凸节点成本，时间交互成本和空间交互成本。在每次决定他们的个人行动时，代理可以访问下一个$ r $ $ - 霍普社区中接下来的$ k $时间步长的本地成本功能的预测。我们的工作提出了一种新颖的在线算法，局部预测控制（LPC），该算法将预测性控制推广到多代理系统。我们表明，LPC在对抗性设置中达到了$ 1 + \ tilde {o}（ρ_T^k） + \ tilde {o}（ρ_S^r）$的竞争比率，其中$ρ_t$ and $ρ_t$和$ρ_s$在$（0，1）$中是$ρ_T$和$ρ_S$，与相对的成本相对且spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial and Spatial。这是在网络在线凸优化的分散预测控制上绑定的第一个竞争比。此外，我们表明，通过降低任何分散的在线算法的竞争比率，对我们结果的$ 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}(ρ_T^k) + \tilde{O}(ρ_S^r)$ in an adversarial setting, where $ρ_T$ and $ρ_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.
