acceptodds
Under review as a conference paper at ICLR 2027

Provably Efficient Exploration for Off-Dynamic Restless Multi-Armed Bandits

Abstract

We study online learning in Restless Multi-Armed Bandits (RMABs) under distributional shift: the agent has access to offline data from a source environment whose dynamics differ from the target by an unknown, arm-specific gap. Ignoring this data wastes a valuable signal and incurs high initial regret; blindly trusting it risks catastrophic failure when the gap is large. We propose ODR-IOB, the first provably safe and adaptive framework for off-dynamic RMABs, built around a Gap-Aware Intersection-of-Balls confidence set construction. The key idea is to maintain a pure-online ball as a safety net, and an offline-augmented ball whose size adapts to a data-driven estimate of the dynamics gap, and plan optimistically over their intersection. The framework is provably never worse than pure online learning, regardless of how large or misleading the gap turns out to be. When the gap is small and the source data is informative, the intersection contracts strictly, yielding a tighter optimistic model and lower regret. We formalize these properties as three simultaneous guarantees: the true dynamics always lie inside the intersection with high probability (coverage); performance never degrades below the pure-online baseline (safety); and regret improves proportionally to the fraction of the state-action space unaffected by the shift (acceleration). Experiments confirm that ODR-IOB significantly outperforms the pure online baseline under small gaps while gracefully degrading to it under large gaps.

Primary area:
reinforcement learning
Keywords:
RL, RMAB, Off-Dyanmic, Learning regret

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_k94jOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper works on the Restless Multi-armed bandit with (possibly biased) offline data. They aim to achieve a best-of-both algorithm, which guarantees (1) if the offline data illustrates the environmental stochasticity correctly, the algorithm is able to achieve smaller regret compared to the fully online learning setting (2) if the offline data is biased, the algorithm still recovers the upper bound of pure online learning algorithm. They design algorithm ODR-IOB to handle the problem setting, achieving these two targets with intuition of algorithm design and performance guarantee. Numeric records validate the efficiency of their algorithm.

Critical strengths
  1. I appreciate the paper is willing to spend enough space to present the intuition of the algorithm design, which is helpful and easy to follow.
  2. The derived upper bound of the regret is meaningful and consistent with the intuition of the algorithm. The instance-independent upper bound of regret should be tight, by comparing it with the K-armed bandit
  3. The paper follows the research standard and covers the required analysis of a theoretical paper.
Critical weaknesses

I am unfamiliar with the topic and I didn't check the proof carefully. Please rectify me if my understanding is wrong.

  1. I think the paper still needs to clarify some notations and improve the presentation, for the rigorousness. See the subsection "Questions For Authors".
  2. Instance-dependent analysis is unclear. But I think it is OK. To my knowledge, that the paper has provided new ideas on the algorithm design and the problem settings. I will check the comments from other reviewers.

Small typo:

  1. line 305, Equation equation
Questions for authors

Please forgive my stupidity if some of them are naive.

  1. I want to confirm whether this paper generalizes the problem setting in "Leveraging (Biased) Information: Multi-armed Bandits with Offline Data, by Cheung Wang Chi and Lyu Lixing", which consider K-armed bandits with offline (possibly biased) data. If not, could you explain the difference?

  2. I would like to confirm the dynamic of the interaction between the agent and the environment. Line 38 suggests "At each time stept tt, a policy πt\pi_t selects a subset of KK arms to activate, where K<NK < N". While the notation table at the page 15 mentions that HH is Episode horizon, which also occurs in the Theorem 5.7. Do you mean there are H horizons in each time step tt? And at each time step tt, the agent needs to first choose K arms, and then takes actions in HH episodes. Then the time step moves to the t+1t+1. In addition, Line 135 suggests that A={0,1}\mathcal{A}=\{0,1\}. Does it mean we should take A=2A=2 in the Theorem 5.7?

  3. I would like to confirm the intuition of the Wasserstein distance. There could be other definition of gap between two distribution. Could you explain why we choose the Wasserstein-1 distance in the definition 3.2, can we replace it with others? For example, 1-norm gap ∥p−q∥1\|p-q\|_1​, or kl-divergence.

  4. I notice that Figure 3 doesn't take the generic metric ρ\rho as the input, which is required in the step 1, calculation of (8). How to specify ρ\rho?

  5. Regarding the presentation appendix C.2, I doubt whether the following presentation is better. We can first present the full formulation of the ELP equation, and then step into constraints. I will expect a lemma, or theorem to conclude that, for example, znt(s,a,s′)=Pnt(s′∣s,a)Pr⁡alg(At round t Pull arm n at state s, take action a)z_n^t(s,a,s')=P_n^t(s'|s,a) \Pr_{\text{alg}}(\text{At round t Pull arm }n\text{ at state }s, \text{ take action } a) xnt=⋯x_n^t=\cdots must be a feasible solution to the optimization formulation.

    It will be easier for me to follow the meaning of solving an optimization problem.

  6. Question 1 regarding (24), if ∣B∣=NSA|\mathtt{B}|=NSA, then (24) becomes O~(H2N2SAT)\tilde{O}(H^2\sqrt{N^2 SAT}). In this case, it can be worse than the bound in (23), contradicting with the conclusion in line 421.

  7. Question 2 ragarding (24). The definition of BB is {(n,s,a):Δn(s,a)>0}\{(n,s,a):\Delta_{n}(s,a)>0\}. That means for two pairs (n′,s′,a′)(n',s',a'), (n′′,s′′,a′′)(n'',s'',a'') such that Δn′(s′,a′)>Δn′′(s′′,a′′)\Delta_{n'}(s',a') > \Delta_{n''}(s'',a'') , they contribute the same to the regret upper bound. I wonder whether it is possible to quantify the impact (n′,s′,a′)(n',s',a'), (n′′,s′′,a′′)(n'',s'',a''), in the case that Δn′(s′,a′)\Delta_{n'}(s',a') is much larger than Δn′′(s′′,a′′)\Delta_{n''}(s'',a''). In other words, are we able to derive partially instance-dependent result? From my intuition, there should be some difference between (n′,s′,a′)(n',s',a') and (n′′,s′′,a′′)(n'',s'',a'') if Δn′(s′,a′)\Delta_{n'}(s',a') is much larger than Δn′′(s′′,a′′)\Delta_{n''}(s'',a'').

I think the answer to the questions 1, 2, 4, 6, 7 are required to support the acceptance, which concerns about a sufficient literature review or rigorous theorem presentation. I will increase my score if the authors are able to clarify these 5 questions. And it will be even better if the authors are able to answer question 3 and 5, which are about the scaffold of designing the algorithm and conducting the analysis.

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

This paper studies the standard restless multi-armed bandit (RMAB) setting with a source dataset. The problem assumes an RMAB instance with NN arms, each arm being a finite Markov Decision Process (MDP) with SS states and AA actions. The reward function is known and bounded in [0,1][0,1], while the transition kernel is unknown. The source dataset provides a source kernel for each arm. The goal is to leverage the source dataset to accelerate learning on the online dataset. The authors assume that the source dataset might not be identical to the online data distribution, and they want to leverage the source dataset to improve the learning process on the online learning problem. The main idea is to construct two confidence sets: one is based on the online dataset, and the other is based on the weighted combination of the online dataset and the source dataset. The intersection of these two confidence sets is used to construct an optimistic policy for exploration. The authors propose an algorithm called ODR-IOB, which follows this idea and provides theoretical guarantees on the regret bound. The main result is a regret bound that depends on the number of shifted state-action pairs, which can be significantly smaller than the total number of state-action pairs. The paper provides theoretical analysis and experimental results to support the proposed algorithm.

Critical strengths

The main result achieves an acceleration of the regret bound by replacing the model complexity term SASA with the number of shifted state-action pairs ∣B∣|\mathcal{B}|. This is a significant improvement when the number of shifted state-action pairs is small, or the source data distribution is identical to the online data distribution.

The authors provide a good illustration of the proposed algorithm to help readers understand the algorithm. The paper is well-written and easy to follow.

The authors conduct experiments to demonstrate the effectiveness of the proposed algorithm. The experimental results show that the proposed algorithm outperforms the baseline algorithms in terms of regret and convergence speed.

Critical weaknesses
  1. The quantity that appears in the main theorem, B\mathcal{B}, seems too strong since it counts the number of state-action pairs that are shifted. Ideally, if we add a small perturbation to the dynamics, the source data might still be useful, but the number of shifted state-action pairs could be large. In practice, it is possible that the perturbation is small but exists in many state-action pairs. In this case, the main theorem does not guarantee any improvement over the baseline algorithm.

  2. There are some problems in the proof of the main theorem. I listed them in the following questions. The main theorem is based on the small-gap condition, which is defined in Theorem 5.4. However, the small-gap condition cannot hold for any (n,s,a,t)(n,s,a,t), even when the empirical gap is zero. This makes the acceleration guarantee in Theorem 5.4 vacuous and contradicts the claim in Lines 1150--1152 that the condition is eventually satisfied for unshifted triples.

Questions for authors

There are some major problems I found in the proof; if the author could resolve these issues I will reconsider my score:

  1. Line 387, Theorem 5.4 defines the small-gap condition at (n,s,a,t)(n, s, a, t) as 2dminΔ~nt(s,a)<δont(s,a)\frac{2}{d_{min}} \tilde{\Delta}^t_n(s,a) < \delta^t_{\rm on}(s,a). However, based on the definition of Δ~nt(s,a)\tilde{\Delta}^t_n(s,a) in Equations 6 and 8, and using ϵnt(s,a)=δont(s,a)\epsilon^t_n(s,a)=\delta^t_{\rm on}(s,a) as stated in Coverage of Cont\mathcal{C}^t_{\rm on} (Equation 43), we have
= \frac{2}{d_{min}}\hat{\Delta}^t_n(s,a) + \frac{d_{max}}{d_{min}} \delta^t_{\rm on}(s,a) \geq \delta^t_{\rm on}(s,a),$$ since $\hat{\Delta}^t_n(s,a)$ is a nonnegative Wasserstein distance and $d_{max}\geq d_{min}>0$. Thus, under this shared confidence-radius definition, the small-gap condition cannot hold for any $(n,s,a,t)$, even when the empirical gap is zero. This makes the acceleration guarantee in Theorem 5.4 vacuous and contradicts the claim in Lines 1150--1152 that the condition is eventually satisfied for unshifted triples. Could the authors clarify how the small-gap condition can be satisfied under the proposed construction and how the acceleration bound in Theorem 5.7(b) follows? 2. In Line 957, $\|P^\star_n - \tilde{P}^t_n\|_1$ is bounded by applying the triangle inequality (Equation 47) and bound the online gap \$ \|\hat{P}^{t}_n - P^\star_n\|_1 \$ by \$ \delta^t_{\\rm on} \$ (Equation 48) and distribution shift $\|P^{\rm src}_n - P^\star_n\|_1$ by $\frac{1}{d_{min}}\tilde{\Delta}^t_n$ (Equation 50). However, the bound on the distribution shift is not correct since $\tilde{\Delta}^t_n$ is defined in Equation 11 as $min\{1, \frac{2}{d_{min}}\tilde{\Delta}^t_n\}$, which is not an upper bound of $\|P^{\rm src}_n - P^\star_n\|_1$. Does it break the proof of Theorem 5.2? If not, how to fix it? (minor issues) 3. Line 256, the second inequality in Equation 9 uses Theorem 5.1. Is it an implication of the confidence-corrected gap (Equations 7 and 8)? Forwarding to Theorem 5.1 seems a little bit gapped. 4. Lines 305, 862, 947, repeated ``equation equation''. 5. Lines 324 - 333, Font size in Figure 2 is too small to read.
Reviewer_QwNzOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies off-dynamics restless multi-armed bandit (RMAB) problems, where the learner has access to offline data from a source domain whose transition dynamics differ from the target domain by an unknown, arm-specific gap. The main contributions are two-fold: (1) This paper proposes ODR-IOB, which is a provably safe and adaptive framework for off-dynamics RMABs and is built on a new confidence set construction method that maintains two confidence balls and takes the intersection. (2) The paper shows that ODR-IOB is never worse than pure online learning in the target domain, regardless of how large the domain gap is. Moreover, a tighter optimistic model and lower regret can be achieved when the gap is small and the source data is informative. Numerical experiments corroborate that ODR-IOB can outperform the pure online learning baseline under small domain gaps and gracefully degrade it under larger domain gaps.

Critical strengths
  • This paper studies off-dynamics RMAB, which is a new setting for the RMAB literature. While off-dynamics RL is quite extensively studied in the RL literature, off-dynamics RMAB presents its own unique challenges and remains open.

  • To handle the off-dynamics issue, the paper proposes a new and interesting idea of constructing two confidence sets (though the proofs might be problematic as described below).

Critical weaknesses
  • My main concern is the correctness of the regret bound in Theorem 5.7. In this paper, the current regret analysis seems to omit the gap between the relaxed LP and a feasible RMAB policy. Specifically, the dynamics regret is defined with respect to an optimal policy that has full knowledge of the per-arm transition kernels under the hard activation budget (i.e., activate at most KK arms in each step). However, based on the pseudo code in Figure 3 and the corresponding ELP in Appendix C.2, per-arm state-action occupancy variables are used in the ELP, and this implies that the ELP operates under a relaxation, i.e., replacing the original hard activation constraint with a soft one. Such relaxation is quite common in the RMAB literature (Xiong et al., 2022; Gast et al., 2023), and it would incur an additional gap in the regret. However, this issue appears not addressed in the paper.

  • Another issue of Theorem 5.7: It is stated that since ∣B∣≤NSA|B| \leq NSA, bound in Eq. (24) is never worse than Eq. (23). However, if one plugs ∣B∣=NSA|B|=NSA into Eq. (24), this would be N\sqrt{N} larger than Eq. 23. This part appears problematic.

  • Moreover, there appears to be one critical error in the construction of the confidence sets. Specifically, by Eqs. (6), (8), and (43), Δ~nt(s,a)=Δ^nt(s,a)+(dmax⁡/2)δont(s,a)\widetilde\Delta_n^t(s,a)=\widehat\Delta_n^t(s,a)+(d_{\max}/2)\delta_{\mathrm{on}}^t(s,a). Therefore, in Eq. (16), we further know (2/dmin⁡)Δ~nt(s,a)≥(dmax⁡/dmin⁡)δont(s,a)≥δont(s,a)(2/d_{\min})\widetilde\Delta_n^t(s,a)\ge(d_{\max}/d_{\min})\delta_{\mathrm{on}}^t(s,a)\ge\delta_{\mathrm{on}}^t(s,a), which implies that the small-gap condition in Theorem 5.4 is impossible. Moreover, the TV-Wasserstein inequality and the blended-center definition imply that the unclipped radius in Eq. (16) is at least δont(s,a)+∣P~nt(⋅∣s,a)−P^nt(⋅∣s,a)∣1\delta_{\mathrm{on}}^t(s,a)+|\widetilde P_n^t(\cdot\mid s,a)-\widehat P_n^t(\cdot\mid s,a)|_1. By the triangle inequality, the offline-augmented ball therefore contains the entire online ball before clipping, so their intersection equals Cont(s,a)\mathcal C_{\mathrm{on}}^t(s,a). Consequently, the stated construction provides no gap-aware tightening before clipping, and any additional restriction must arise from clipping rather than the mechanism claimed in Theorem 5.4.

  • The paper assumes that the source prior model is exact, or equivalently the source dataset size is sufficiently large so that the error is negligible. This completely ignores the coverage issue and the estimation error of the source domain. However, the exact PsrcP_{src} is likely not available in practice, and the source dataset coverage can possibly be limited as it is collected under some behavior policy.

Given the above concerns, I am leaning towards rejection for now, but I will be willing to adjust the score if the above fundamental issues can be addressed.

References:

  • Xiong et al., “Reinforcement Learning Augmented Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits,” AAAI 2022.

  • Gast et al., ”Linear Program-Based Policies for Restless Bandits: Necessary and Sufficient Conditions for (Exponentially Fast) Asymptotic Optimality,” Mathematics of Operations Research, 2023.

Questions for authors
  • Regarding Theorem 5.7, can the authors clarify the issues about the relaxation in RMAB and the dependency on NN?

  • Regarding the constructed confidence sets, can the authors confirm if the small-gap condition in Theorem 5.4 is indeed impossible under the current design and if the offline-augmented ball contains the entire online ball before clipping?

  • Can the authors further justify the assumption that the source prior model is exact?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.