acceptodds
Under review as a conference paper at ICLR 2027

BIRD: Belief-Encoder Index Restless Diffusion for Partially Observable RMABs

Abstract

Restless multi-armed bandits (RMABs) provide a principled framework for resource-constrained sequential decision-making, yet classical Whittle-index methods assume fully observable, discrete states and known dynamics. These assumptions break down in partially observable RMABs with continuous latent states and unknown or drifting dynamics, motivating stochastic score models beyond deterministic rankings. We present BIRD(Belief Encoder Index Restless Diffusion), a scalable score-based algorithm that uses a shared BeliefEncoder and diffusion actor to sample stochastic priority scores, together with a global Top-K projection to enforce the hard budget. We show that the Top-K projection maps score-space policy mirror descent (PMD) to a corresponding update over budget-feasible RMAB actions. Across synthetic and MIMIC-derived environments, BIRD outperforms random, greedy, NeurWIN, PPO, and learned-rollout baselines. Actor ablations isolate the benefit of the shared per-arm diffusion actor over deterministic MLP actor, Gaussian actor, and global joint-arm diffusion variants.

Primary area:
reinforcement learning
Keywords:
Restless Multi-Armed Bandits, Partially Observable RMABs, Non-Stationary Environments, Reinforcement Learning, Diffusion Policies, Resource Allocation, Constrained Decision Making

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_oddzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates partially observable restless multi-armed bandits (RMABs) in continuous latent spaces where the dynamics are unknown or vary over time. The proposed method, BIRD, consists of modeling the actor’s priorities using a shared belief encoder and a diffusion actor, combined with selection via a Top-K projection. It has been theoretically demonstrated that this approach yields updates that satisfy budget constraints. Furthermore, experiments confirm its effectiveness.

Critical strengths

In the field of partially observable restless multi-armed bandits (RMABs), a significant method has been proposed as a solution to the issue of not satisfying the assumptions of conventional RMAB methods.

The proposal is presented in a structure that is easy to understand from a theoretical perspective and includes theoretical guarantees.

From these perspectives, this is a meaningful proposal that holds promise for the future development of this field.

Critical weaknesses

This paper argues that a new method is necessary because the classical Whittle index method cannot be applied to partially observed RMABs, given that it assumes discrete states. On the other hand, several studies on partially observed RMABs have been published, such as [1]–[4]. Given this context, concerns arise as to whether the problem formulation in this paper is appropriate.

(There is a possibility that the authors are claiming achievements while concealing issues that have already been resolved.) This point constitutes a major problem regarding the structure of this paper.

Regarding methodological questions: How is the value of K in TopK determined? It is difficult to understand how performance varies with K based solely on the two results for K = 5 and K = 20. If setting K leads to catastrophic results, it is difficult to highly evaluate the validity of the results at this stage.

[1] J. Kuhn et al., Exploration vs Exploitation with Partially Observable Gaussian Autoregressive Arms, International Conference on Performance Evaluation Methodologies and Tools, 2014

[2] Y. Zhao et al., Towards a Pretrained Model for Restless Bandits via Multi-arm Generalization, IJCAI 2024

[3] A. Mate et al., Collapsing Bandits and Their Application to Public Health Intervention, NeuRIPS 2020

[4] K. Liu, Relaxed Indexability and Index Policy for Partially Observable Restless Bandits, Management Science Vol.17 No.12

Questions for authors

Please clarify how this study relates to previous research regarding partially observed RMABs.

Please explain the methodology for setting K and the changes associated with different values of K.

1 comment

We thank the reviewer for their careful review and feedback. We briefly summarize the response to your questions below.

Q1 connection to other partially observed RMABs: the major difference is the use of transformer to encode the historical trajectory and the use of diffusion head to predict the index. Our model benefits from the expressiveness of transformer and the multimodality and exploration benefit of diffusion model. We will add more experiments to compare with other partially observed RMAB methods to validate the improvement led by transformer and diffusion model separately.

Q2 choice of parameter K: Our experiments evaluate different problem sizes and budgets, including (N, K) = (20, 5), (40, 10), and (100, 25), where K is approximately 25% of N. These experiments only demonstrate the scalability of BIRD under different resource budgets, not aiming to test the change in terms of different K.

Reviewer_xoqGOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

BIRD addresses partially observable restless multi-armed bandits with continuous latent states and unknown or drifting dynamics. A shared Transformer encodes each arm's history, a shared per-arm diffusion actor samples priority scores, and a global Top-K projection enforces the per-period activation budget. Twin per-arm critics additively approximate the joint action value and supply weights for Q-weighted denoising. Proposition 5.1 shows that the Top-K pushforward of an ideal score-space policy mirror descent target yields the corresponding KL-regularized update over feasible actions. Experiments include a two-state sanity check, stationary and drifting synthetic environments, a MIMIC-III-calibrated simulator, actor, encoder, critic and history-length ablations, and scale-transfer and timing reports.

Critical strengths

1.The architecture is well matched to RMAB structure. Shared per-arm modules support permutation equivariance and reuse across arm counts, while separating continuous scores from global Top-K selection enforces the hard activation budget. Proposition 5.1 and its proof explain how the ideal score-space target induces a feasible-action update. The combination of scalability and budget feasibility is the paper's strongest positive aspect. 2.The evaluation spans a two-state setting with computable Whittle indices, drifting dynamics, and a clinical-data-calibrated simulator. The paper provides extensive component ablations, inference timings, a code link, and explicit simulation-related ethical boundaries. BIRD has the highest reported non-oracle mean returns in the main comparisons (Tables 3-5), and the factor tests support a stronger relative advantage under unknown dynamics. This is not uniform dominance: simpler baselines are stronger in the known-dynamics synthetic tests and the two-state check (Tables 10 and 12).

Critical weaknesses

1.Results across independent training seeds would strengthen the evidence. Figure 3 and Table 3 report means and standard deviations across 100 evaluation episodes, while Table 7 explicitly uses one training seed per critic variant, with checkpoints different from those in the main comparison. The number of independent training seeds used in the main comparisons is not specified. Repeated training under matched budgets, with mean returns and confidence intervals across training seeds, would clarify whether the gains persist across initializations. The current error bars quantify variation across evaluation episodes, not variability across independent training runs. 2. A targeted diagnostic of the additive critic's approximation error would be useful. The paper already compares task returns for per-arm twin, per-arm single and joint twin critics (Table 7), and explicitly describes additivity as a structured approximation rather than an exact decomposition (Section 4.1). A small, tractable RMAB could compare the additive estimate with the exact joint action value under the same policy to characterize error under budget coupling. This would be an optional diagnostic beyond the existing return-based ablation.

Questions for authors

1.How many independent training seeds were used for the main comparisons? Could you provide multi-seed results for BIRD and the main baselines under matched training budgets, reporting mean returns and confidence intervals across training seeds separately from variation across evaluation episodes? 2.As an optional follow-up to Table 7, could you report how the additive critic's estimation error varies with activation budget in a small, tractable RMAB? Within each budget setting, compare with exact joint Q values for the same fixed policy, matching the state or belief conditioning, horizon and discount. This would clarify the approximation under different budget constraints.

1 comment

We thank the reviewer for the constructive feedback and thoughtful suggestions. We plan to adopt the reviewer's suggestions to revise our experiments. Please find our short response below.

Q1 number of training seeds: we only ran 1 training seed, but evaluated on 100 evaluation seeds to test the performance on different RMAB instances. We are running multiple training seeds now and will add those results to the paper.

Q2 additive critic estimation error: We thank the reviewer's suggestion and we will add an experiment to estimate the additive critic's estimation error. This in practice can be challenging as non-additive critic and the optimal value of coupled RMABs can be computationally expensive to solve, which as the reviewer suggested, maybe a smaller RMAB would be a good starting point to verify. We will also try to see if there is a better way to measure the estimation error on larger RMABs.

Reviewer_KtmdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes BIRD (Belief-Encoder Index Restless Diffusion) for partially observable restless multi-armed bandits with continuous latent states and unknown or drifting dynamics. A shared Transformer encodes each arm’s history, a per-arm diffusion actor generates priority scores, and Top-K selection enforces the activation budget. An additive critic trains the actor through Q-weighted denoising.

The main theoretical result shows that applying Top-K to an ideal score-space policy mirror descent update yields the corresponding KL-regularized update over feasible binary actions.

Across synthetic RMABs, a MIMIC-III-derived ICU simulator, and a fully observable benchmark, BIRD achieves the highest mean return among evaluated non-oracle methods in the three main environments. Ablations examine actor alternatives, the belief encoder, auxiliary prediction loss, and critic design.

Critical strengths
  1. A scalable architecture for partially observable RMABs. Shared history encoding, per-arm score generation, and global Top-K selection offer a practical approach when classical Whittle-index computation is infeasible. Parameter sharing accommodates different arm counts without modifying the per-arm networks, addressing settings with continuous latent states, partial observability, and unknown dynamics.

  2. Encouraging results across environments. BIRD achieves the highest mean return among evaluated non-oracle methods across three main environments and multiple problem sizes. The drifting setting tests adaptation to changing dynamics, while actor ablations support the shared diffusion design over tested alternatives. Together, these results provide promising preliminary evidence of practical value.

Critical weaknesses
  1. The PMD justification does not cover the implemented factorized actor.

Proposition 5.1 correctly shows that an unrestricted joint score-space PMD update induces the corresponding PMD update over feasible actions through Top-K. BIRD, however, samples scores independently:

πθ(w∣z)=∏i=1Nπθ(wi∣zi).\pi_\theta(w\mid z)=\prod_{i=1}^{N}\pi_\theta(w_i\mid z_i).

The ideal target,

π+(w∣z)∝πold(w∣z)exp⁡ ⁣(Q(z,TopK⁡(w))η),\pi^+(w\mid z)\propto \pi_{\mathrm{old}}(w\mid z) \exp\!\left(\frac{Q(z,\operatorname{TopK}(w))}{\eta}\right),

generally introduces dependencies through Top-K and may therefore lie outside this factorized family.

Consequently, per-arm weighted denoising need not recover the joint PMD target or its induced action distribution, even with unlimited data and perfect optimization. Since the proposition is the central theoretical justification for training, the authors should establish a result for the restricted actor or clarify the approximation and its implications.

  1. The experiments do not establish robust gains attributable to diffusion.

The favorable mean returns appear to rely mainly on 100 evaluation episodes, with unclear variability across independent training runs. Appendix Table 7 explicitly uses one training seed. The deterministic MLP’s near-random performance in the drifting environment—2425.3 versus BIRD’s 7042.5—also warrants investigation into training stability and tuning.

The motivation for stochastic policies needs qualification. Under standard discounted finite-action assumptions, a risk-neutral belief-state MDP admits an optimal deterministic policy; latent ranking uncertainty alone therefore does not imply an intrinsic benefit from randomization.

Independently tuned deterministic and stochastic baselines across multiple training seeds would help separate diffusion’s expressiveness from exploration and optimization effects.

Questions for authors
  1. PMD and factorization. What guarantee applies to the factorized per-arm actor when the ideal Q-reweighted joint target does not factorize? Does weighted per-arm denoising recover the target’s marginals, and what follows for the induced Top-K action distribution?

  2. Training robustness. How many independent training seeds were used in the main comparisons and actor ablations? Please report variability across seeds and clarify whether MLP, Gaussian, and diffusion actors received comparable tuning and computational budgets.

  3. Role of stochasticity. Since the belief-state formulation generally admits an optimal deterministic policy, do stochastic scores help through exploration, optimization, or representational capacity? Can experiments distinguish these explanations?

  4. Additive critic. How sensitive is BIRD to approximating joint action values as a sum of per-arm values under a shared activation budget? Does the critic preserve useful action rankings when the true values contain substantial non-additive interactions?

2 comments

I did not see a response from the authors yet; will keep my score as is for now.

We thank the reviewer for their constructive feedback. Please find our brief response below.

  • Q1 PMD and factorization: We agree that the factorized per-arm diffusion actor used in BIRD may not exactly represent this joint target, and that additional analysis is needed to characterize the resulting approximation error. This is the major missing piece in our theoretical analysis, and we are working on it to improve the paper.

  • Q2 Training robustness: We ran only 1 seed for training the model, but evaluated the performance on 100 RMAB instances at test time to get the error bar. We will add larger experiments in our paper to strengthen the experiments.

  • Q3 Role of stochasticity: stochasticity in training usually helps with exploration and convergence. The same phenomenon has been observed in online RL with diffusion policy [1,2,3,4]. We believe these properties are particularly relevant for partially observable RMABs with unknown and drifting dynamics. We will further clarify this motivation and investigate the respective contributions of exploration, optimization, and expressiveness in our revision.

  • Q4 Additive critic: The additive critic is motivated by the classical Lagrangian relaxation of RMABs, under which the budget constraint is relaxed and the problem decomposes into independent single-arm decision problems. In this setting, the relaxed joint Q-function admits an additive decomposition. We acknowledge that this decomposition is generally not exact under the original hard budget constraint. BIRD adopts the additive structure as a scalable inductive bias for critic learning, while enforcing the hard budget through Top-K selection. Our goal is to learn useful relative action values for policy improvement rather than exactly recover the joint Q-function.

[1] "Efficient Online Reinforcement Learning for Diffusion Policy" Haitong Ma, Tianyi Chen, Kai Wang, Na Li, Bo Dai, ICML 2025 [2] S. Ding et al. "Diffusion-based Reinforcement Learning via Q-weighted Variational Policy Optimization." NeurIPS, 2024. [3] A. Z. Ren et al. "Diffusion Policy Policy Optimization." arXiv:2409.00588, 2024. [4] L. Yang et al. "Policy Representation via Diffusion Probability Model for Reinforcement Learning." arXiv:2305.13122, 2023.

Comments on the paper

1 comment

We sincerely thank all the reviewers for their time and effort in evaluating our paper and providing thoughtful and constructive feedback.

We apologize for our delayed response. We have been carefully considering the reviewers' concerns and working to strengthen both the theoretical analysis and experimental evaluation. After careful consideration, we have decided to withdraw the paper from this review cycle to allow more time for these improvements.

We genuinely appreciate the reviewers' insightful comments and suggestions, which have helped us identify important directions for improving our work. We will take this feedback seriously and incorporate it into a substantially improved version of the paper for future submission.

Thank you again for your time, thoughtful feedback, and valuable contributions to improving our research.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.