Lagrangian Relaxation for Multi-Action Partially Observable Restless Bandits: Heuristic Policies and Indexability

2025-08-30 · Rahul Meshram, Kesav Kaza arxiv

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.

📄 PDF Abstract BibTeX arXiv:2509.00415

Code (0)

등록된 구현이 없습니다.

Tasks

Recommendation Systems Multi-Armed Bandits

Bayes-Optimal Effort Allocation in Crowdsourcing: Bounds and Index Policies

2015-12-31 · Weici Hu, Peter I. Frazier

We consider effort allocation in crowdsourcing, where we wish to assign labeling tasks to imperfect homogeneous crowd workers to maximize overall accuracy in a continuous-time Bayesian setting, subject to budget and time…

Addressing Myopic Constrained POMDP Planning with Recursive Dual Ascent

2024-03-26 · Paula Stocco, Suhas Chundi, Arec Jamgochian, Mykel J. Kochenderfer

Lagrangian-guided Monte Carlo tree search with global dual ascent has been applied to solve large constrained partially observable Markov decision processes (CPOMDPs) online. In this work, we demonstrate that these globa…

Decision Making

C-IDS: Solving Contextual POMDP via Information-Directed Objective

2026-02-03 · Chongyang Shi, Michael Dorothy, Jie Fu arxiv

We study the policy synthesis problem in contextual partially observable Markov decision processes (CPOMDPs), where the environment is governed by an unknown latent context that induces distinct POMDP dynamics. Our goal …

Deep reinforcement learning driven inspection and maintenance planning under incomplete information and constraints

2020-07-02 · C. P. Andriotis, K. G. Papakonstantinou

Determination of inspection and maintenance policies for minimizing long-term risks and costs in deteriorating engineering environments constitutes a complex optimization problem. Major computational challenges include t…

Bayesian Inference Deep Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing

2014-01-23 · Alexander M. Rush, Michael Collins

Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tu…

Combinatorial Optimization