针对多动作不可观测马尔可夫带子问题，提出基于拉格朗日松弛的近似解法与启发式策略。
Lagrangian Relaxation for Multi-Action Partially Observable Restless Bandits: Heuristic Policies and Indexability
- 采用拉格朗日松弛结合点值迭代和在线回溯策略逼近最优值函数。
- 在预算约束下实现多动作不可观测带子的长期折扣收益优化，适用于公共健康干预等场景。
- 揭示了点值迭代与在线回溯策略的理论性质，拓展了威特勒指数政策的适用范围。
部分可观测的随机多臂老虎机问题在推荐系统、通信系统、公共卫生干预及运筹学中广泛应用。本文研究多动作部分可观测非平稳多臂老虎机问题，这是经典非平稳多臂老虎机的推广：1）每个老虎机具有有限状态且当前状态不可观测；2）每个老虎机有多个可选动作（超过两个）。以公共卫生干预规划为例，我们建立模型并提出长期折扣优化目标。每个老虎机的状态按马尔可夫过程演化，且演化依赖于所采取的动作；状态不可观测，但可观测到有限个反馈信号。每个老虎机根据所执行动作产生奖励，智能体受预算约束。各老虎机相互独立，但在智能体层面通过预算弱耦合。我们首先分析该问题的拉格朗日界方法。由于有限状态、有限动作的部分可观测马尔可夫决策过程（POMDP）的最优值函数计算困难，拉格朗日界计算也极具挑战。为此，我们提出基于点值迭代（PBVI）和在线回溯策略的近似方法。进一步分析价值函数性质，提供对PBVI与在线回溯策略的理论洞察。研究多动作部分可观测非平稳带子的启发式策略，并讨论威特勒指数策略在此模型中的局限性。
原文摘要 · Abstract (English)
Partially observable restless multi-armed bandits have found numerous applications including in recommendation systems, communication systems, public healthcare outreach systems, and in operations research. We study multi-action partially observable restless multi-armed bandits, it is a generalization of the classical restless multi-armed bandit problem -- 1) each bandit has finite states, and the current state is not observable, 2) each bandit has finite actions. In particular, we assume that more than two actions are available for each bandit. We motivate our problem with the application of public-health intervention planning. We describe the model and formulate a long term discounted optimization problem, where the state of each bandit evolves according to a Markov process, and this evolution is action dependent. The state of a bandit is not observable but one of finitely many feedback signals are observable. Each bandit yields a reward, based on the action taken on that bandit. The agent is assumed to have a budget constraint. The bandits are assumed to be independent. However, they are weakly coupled at the agent through the budget constraint. We first analyze the Lagrangian bound method for our partially observable restless bandits. The computation of optimal value functions for finite-state, finite-action POMDPs is non-trivial. Hence, the computation of Lagrangian bounds is also challenging. We describe approximations for the computation of Lagrangian bounds using point based value iteration (PBVI) and online rollout policy. We further present various properties of the value functions and provide theoretical insights on PBVI and online rollout policy. We study heuristic policies for multi-actions PORMAB. Finally, we discuss present Whittle index policies and their limitations in our model.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。