基于模型预测控制的策略几乎最优解决随机带子问题
Model Predictive Control is Almost Optimal for Restless Bandit
- 用滚动时域的线性规划生成非平稳控制策略
- 理论证明次优性差距为1/√N，特定条件下指数级收敛
- 方法简单易实现，适用于更广泛的约束马尔可夫决策过程
我们研究离散时间无限时域平均奖励随机马尔可夫带子（RMAB）问题。提出一种基于模型预测控制的非平稳策略，采用滚动计算时域τ。每个时间槽中求解一个τ时域线性规划，仅保留第一个控制值用于实际决策。该方法假设极少，且能以τ和臂数N量化次优性损失。一般情况下次优性差距为O(1/√N)，在局部稳定性条件下可达exp(−Ω(N))。证明基于动态控制中的耗散性框架。该策略易于实现，在实践中显著优于现有方法。此外，该方法及证明框架可推广至更一般的约束马尔可夫决策过程，对快速增长的RMAB研究社区具有重要价值。
原文摘要 · Abstract (English)
We consider the discrete time infinite horizon average reward restless markovian bandit (RMAB) problem. We propose a \emph{model predictive control} based non-stationary policy with a rolling computational horizon $τ$. At each time-slot, this policy solves a $τ$ horizon linear program whose first control value is kept as a control for the RMAB. Our solution requires minimal assumptions and quantifies the loss in optimality in terms of $τ$ and the number of arms, $N$. We show that its sub-optimality gap is $O(1/\sqrt{N})$ in general, and $\exp(-Ω(N))$ under a local-stability condition. Our proof is based on a framework from dynamic control known as \emph{dissipativity}. Our solution easy to implement and performs very well in practice when compared to the state of the art. Further, both our solution and our proof methodology can easily be generalized to more general constrained MDP settings and should thus, be of great interest to the burgeoning RMAB community.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。