Research map / Bandits and online learning / RL theory and MDPs
Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UCMD-ARMAB, an episodic RL algorithm for adversarial restless multi-armed bandits with unknown transitions and bandit feedback, combining UCRL-style confidence sets, OMD over occupancy measures, biased overestimating reward estimators, and an index policy; achieves Õ(H√T) regret.
Problem
Learning in episodic restless multi-armed bandits with unknown transition kernels, adversarial (arbitrarily changing) rewards, bandit feedback, and a hard per-epoch activation constraint of B arms.
Approach
Relaxes the hard activation constraint to an average one, solves the resulting problem over time-dependent state-action-state occupancy measures via KL-regularized online mirror descent inside confidence sets, uses an optimistic biased importance-weighted reward estimator for bandit feedback, and converts the solution into a feasible reward-maximizing index (RMI) policy.
Key results
- Proves Õ(H√T) regret for UCMD-ARMAB under bandit feedback with unknown transitions and adversarial rewards, the first Õ(√T) bound in this setting (√H worse than stochastic RMAB bounds).
- In numerical studies on CPAP and deadline scheduling simulations, UCMD-ARMAB achieves higher accumulated reward than RMAB-UCRL under adversarial rewards.
- Regret of UCMD-ARMAB is sublinear in the numerical experiments, while RMAB-UCRL's regret reportedly grows much faster under adversarial settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCMD-ARMAB instead of RMAB-UCRL | Adversarial RMAB · CPAP and deadline scheduling | accumulated reward | Helped |
| Use UCMD-ARMAB instead of RMAB-UCRL | Adversarial RMAB · CPAP and deadline scheduling | regret | Helped |
Surprising findings
- The RMAB-UCRL baseline's regret is reported to increase exponentially under adversarial settings.
Limitations
- Regret is sqrt(H) worse than the best stochastic RMAB bound.
- Relaxed occupancy-measure problem requires solving a constrained convex program each episode and the index policy is only asymptotically optimal.
- Experiments are limited to two simulated applications against a single baseline.
Experimental setup
Benchmarks: CPAP therapy RMAB simulation deadline scheduling RMAB simulation
Metrics: accumulated reward accumulated regret
Baselines: RMAB-UCRL
Builds on: UCRL2 online mirror descent occupancy-measure methods for adversarial MDPs Whittle index
Closest papers by meaning
- DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback (ICLR 2025 · similarity 0.90)
- Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints (AAAI 2024 · similarity 0.89)
- The Bandit Whisperer: Communication Learning for Restless Bandits (AAAI 2025 · similarity 0.89)
- Reinforcement learning with combinatorial actions for coupled restless bandits (ICLR 2025 · similarity 0.88)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.88)
- Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.