标题： 用于具有不完全观测的 restless bandits 的低复杂度算法 显示英文标题

标题： Low-Complexity Algorithm for Restless Bandits with Imperfect Observations

摘要： 我们考虑一类在随机优化、强化学习和运筹学中有广泛应用的 restless bandit 问题。 我们考虑$N$个独立的离散时间马尔可夫过程，每个过程都有两个可能的状态：1 和 0（“好”和“坏”）。 只有当一个过程处于状态 1 并且被观察到时才会产生奖励。 目标是在无限时间范围内最大化回报的期望折扣总和，同时满足每一步只能观察$M$ $(<N)$ 个过程的约束条件。 观察是容易出错的：已知状态 1（0）会被观察为 0（1）的概率。 由此可知，在任何时间$t$，过程$i$处于状态 1 的概率。 该系统可以建模为一个具有不可数基数信息状态空间的 restless 多臂老虎机问题。 即使具有有限状态空间的 restless bandit 问题，在一般情况下也是 PSPACE-HARD 的。 我们提出了一种简化这类 restless bandits 动态规划方程的新方法，并开发了一个低复杂度的算法，该算法表现出良好的性能，并易于扩展到具有观测误差的一般 restless bandit 模型。 在某些条件下，我们建立了 Whittle 指数的存在性（可索引性）及其与我们算法的等价性。 当这些条件不成立时，我们通过数值实验展示了我们的算法在一般参数空间中的近似最优性能。 最后，我们理论证明了我们的算法在同质系统中的最优性。 显示英文摘要

摘要： We consider a class of restless bandit problems that finds a broad application area in stochastic optimization, reinforcement learning and operations research. We consider $N$ independent discrete-time Markov processes, each of which had two possible states: 1 and 0 (`good' and `bad'). Only if a process is both in state 1 and observed to be so does reward accrue. The aim is to maximize the expected discounted sum of returns over the infinite horizon subject to a constraint that only $M$ $(<N)$ processes may be observed at each step. Observation is error-prone: there are known probabilities that state 1 (0) will be observed as 0 (1). From this one knows, at any time $t$, a probability that process $i$ is in state 1. The resulting system may be modeled as a restless multi-armed bandit problem with an information state space of uncountable cardinality. Restless bandit problems with even finite state spaces are PSPACE-HARD in general. We propose a novel approach for simplifying the dynamic programming equations of this class of restless bandits and develop a low-complexity algorithm that achieves a strong performance and is readily extensible to the general restless bandit model with observation errors. Under certain conditions, we establish the existence (indexability) of Whittle index and its equivalence to our algorithm. When those conditions do not hold, we show by numerical experiments the near-optimal performance of our algorithm in the general parametric space. Last, we theoretically prove the optimality of our algorithm for homogeneous systems.