标题： 模型预测控制对于不安分的多臂老虎机几乎是最佳的 显示英文标题

标题： Model Predictive Control is Almost Optimal for Restless Bandit

摘要： 我们研究了离散时间无限时域平均奖励的不安分马尔可夫多臂老虎机（RMAB）问题。 我们提出了一种基于\emph{模型预测控制}的非平稳策略，具有滚动计算时域$\tau$。 在每个时隙，该策略求解一个$\tau$时域线性规划，其第一个控制值被保留为 RMAB 的控制。 我们的解决方案假设最少，并以$\tau$和手臂数量$N$来量化最优性的损失。 我们证明了其次优性差距一般为$O(1/\sqrt{N})$，在局部稳定性条件下为$\exp(-\Omega(N))$。 我们的证明基于动态控制领域的一个框架，称为\emph{耗散性}。 与最先进的方法相比，我们的解决方案易于实现且在实践中表现出色。 此外，我们的解决方案和证明方法都可以轻松推广到更一般的约束MDP设置，因此，应该会引起新兴的RMAB社区的极大兴趣。 显示英文摘要

摘要： 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 $\tau$. At each time-slot, this policy solves a $\tau$ 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 $\tau$ and the number of arms, $N$. We show that its sub-optimality gap is $O(1/\sqrt{N})$ in general, and $\exp(-\Omega(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.