DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback
Authors: GUOJUN XIONG
Ujwal Dinesha
Debajoy Mukherjee
Jian Li
Srinivas Shakkottai
Venue: ICLR 2025 Poster (2025)
Keywords: Restless Multi-Armed Bandits
Preference Feedback
Online Preference Learning
Primary area: reinforcement learning

Abstract: Restless multi-armed bandits (RMAB) has been widely used to model constrained sequential decision making problems, where the state of each restless arm evolves according to a Markov chain and each state transition generates a scalar reward. However, the success of RMAB crucially relies on the availability and quality of reward signals. Unfortunately, specifying an exact reward function in practice can be challenging and even infeasible. In this paper, we introduce Pref-RMAB,  a new RMAB model in the presence of preference signals, where the decision maker only observes pairwise preference feedback rather than scalar reward from the activated arms at each decision epoch. Preference feedback, however, arguably contains less information than the scalar reward, which makes Pref-RMAB seemingly more difficult. To address this challenge, we present a direct online preference learning (DOPL) algorithm for Pref-RMAB to efficiently explore the unknown environments, adaptively collect preference data in an online manner, and directly leverage the preference feedback for decision-makings. We prove that DOPL yields a sublinear regret. To our best knowledge, this is the first algorithm to ensure $\tilde{\mathcal{O}}(\sqrt{T\ln T})$ regret for RMAB with preference feedback. Experimental results further demonstrate the effectiveness of DOPL.

Published as a conference paper at ICLR 2025
DOPL: DIRECT ONLINE PREFERENCE LEARNING FOR RESTLESS BANDITS WITH PREFERENCE FEEDBACK
Guojun Xiong'; Ujwal Dinesha', Debajoy Mukherjee', Jian Li Srinivas Shakkottai
Harvard University, Texxas A&M University, "Stony Brook University
ABSTRACT
Restless multi-armed bandits (RMAB) has been widely used model constrained sequential decision making problems, where the state of cach restless arm evolves according to a Markov chain and each state transition generates scalar reward. However, the success of RMAB crucially relies on the availability and quality of reward signals. Unfortunately, specifying an exact reward function in practice can be challenging and even infeasible. In this paper, we introduce PREF-RMAB, a new RMAB model in the presence of preference signals, where the decision maker only observes pairwise preference feedback rather than scalar reward from the activated arms at each decision epoch. Preference feedback, however, arguably contains less information than the scalar reward, which makes PREF-RMA AB seemingly more difficult. To address this challenge, we present a direct online preference learning (DOPL. algorithm for PREE-RMAB to efficiently explore the unknown environments, adaptively collect preference data in an online manner, and directly leverage the preference feedback for decision-makings. We prove that DOPL yields a sublinear regret. To our best knowledge, this is the first algorithm to ensure Ó (n'TIn') regret for RMAB with preference feedback. Experimental results further demonstrate the effectiveness of DOPI.
INTRODUCTION
The restless multi-armed bandits (RMAB) problem (Whittle| 1988) a time slotted game between decision maker (DM) and the environment. In the standard RMAB model, each "restless" arm is described by a Markov decision process (MDP) (Puterman) 1994). and evolves stochastically according to two different transition functions, depending whether the arm is activated or not. Scalar rewards are generated with each transition. The goal of the DM is to maximize the total expected reward under an instantaneous constraint that at most B out of N arms can be activated any decision epoch. Although RMAB has been widely used to study constrained sequential decision
making problems (Meshram et al., 20166] Bertsimas & Niño-Mora 2000 Yu et al. 2018 Borkar et al.) 2017] Killian et al.] [021]] Mate et al. [021] Xiong et al. 2023a it is notoriously intractable
due the explosion of state space (Papadimitriou & Tsitsiklis 1994). To address this issue, there
are extensive studies on developing low-complexity index policies (Whitle, 1988, Larrañaga et al. 2014, Bagheri Scaglione 2015 Verloop 2016 Zhang Frazier| 2021] for offline RMAB and
reinforcement learning (RL) algorithms (Tekin & Liu Liu|2011]Cohern et [2014) et al. 2019 JJng
et al. |202b/|Avrachenkkr Avrachenkov & Borkar 2022 Xiong & Li. 2023 Wang et al. [2024a] Chen et al. (2024) for online RMAB.
Tewari 2019 Wang et al. 2020 Nakhleh et
However, the success of these index polices and RI. algorithms for the standard RMAB crucially relies on the availability and quality of reward signals or reward feedback. Unfortunately, specifying an exact reward function in practice can be challenging, and obtaining the precise reward feedback may be even infeasible (Wirth et al., 2017 Casper et al. 2023). Instead, it is often much easier, faster and less expensive to collect preference feedback (e.g.. provided by humans). This is especially pronounced for existing RMAB applications in online advertisement (Meshram et al.) 2016) and
healthcare (Killian et al. 2021 Mate et al. 2021 2020). For example, to understand the liking for a given pair of products (A, B) in online ads, it is much easier for users answer preference-based
"This work done when G. Xiong was PhD student Stony Brook University.

---

Published as a conference paper at ICLR 2025
queries like: "Do you prefer product A over B?", rather than the absolute counterpart, "How much do you score products A and B in a scale of [0-10]?"
Learning from preference feedback has gained much popularity in the machine learning community, from the famous ducling bandit problem (Yue et al. 2012) to the more recent reinforcement learning from human feedback (RLHF) (Christiano et al.] [ Zi7glee et al. 2019)) e.g., for the large language model (LLM) alignment (Ouyang et al. 2022) Motivated by this and to address the limitation of the standard RMAB model, we propose a new RMAB model in the presence of preference feedbuck, dubbed as
Real-world applications that can be modeled as PREF-RMAI problems are presented in Appendix B] Like the standard RMAB, the DM in FREF-RMAB still activates a subset of B arms at each decision epoch. Unlike the standard RMAB, the DM in PREF-RMA cannot directly observe a scalar reward from each activated arm, and instead can only observe a pairwise comparison feedback from the activated subset of arms. Preference feedback, however, arguably contains less information than the scalar reward, which makes PREF-RMAB seemingly more difficult. A thorough understanding of how the preference feedback influences the DM in PREF-RA -MEB remains clusive. Conseauently. this promnts us to DOse the following question:
Can we design efficient RL algorithms for PREF-RMAB with sublinear regret guarantees?
In response to the this question, a straightforward method as inspired by RLHF is to learn a scalar re- ward function to represent the preference feedback of humans, and then apply existing RL algorithms for RMAB with this estimated reward function to the PREF-RMAB problem. The downside of directly applying this RLHF method to PREF-RMAP RMAB is its complexity and insufficiency. The limited theoretical analysis of RLHF (Chen et al. 2022 Zhu et al. 2023 Saha et al. 2023 Du et al. 2024) typically assumes a linear reward function, i.c., there exists a known feature mapping to specify the feature vectors of state-action pairs. However, the feature mapping in practice is often unknown and fine-tuning its dimension can be resource-intension and prone error. In view of these issues, there is an innovative line of work that directly learns from preferences without explicit reward modeling, such the popular direct preference optimization (DPO) (Rafailov et al.
2024) and among others
(Zhao et al. [003]] Azar et al., [024] Ethayarajh et al. 2024] Tang et al. 2024). However, most of the latest RLHF and DPO based methods are considered offline and provided with a given and pre-collected human preference (and transition) dataset, leading to the problem of overoptimization (Xiong et al., 2023b), while the DM in PREF-RMAB often interacts with unknown environments in an online manner to model constrained sequential decision making problems in aforementioned RMAB applications.
In this paper, we consider the online PREF-RMAB, and show how to directly leverage the preference feedback to design a provably efficient RI algorithm for PREF-RMAB without explicit reward modeling. Specifically, we develop Direct Online Preference Learning (DOPL), an episodic RL algorithm that optimizes the same objective as the standard RMAB problem but can efficiently explore the unknown environment, adaptively collect preference data in an online manner, and directly leverage the preference feedback to make decisions for RMAB.
First, to handle unknown transitions of each arm, construct confidence sets to guarantec the true ones lie in these sets with high probability (Section B.J). Second, by assuming a Bradley-Terry (BT) model (Bradley & Terry 1952), DOPL may use the results of comparison between any pair of activated arms to update the estimate of the underlying unknown preference model. However, the success of this empirical preference estimation requires DOPL activate any arm in any state frequently, which often, in practice, are hardly feasible. To handle the unknown preference model, we design novel preference inference. Our key insight here is that although some arms in some states may not be visited frequently. we can still infer the empirical average of its preference via the other arms' empirical preference estimations. Importantly, our preference inference not only significantly reduces the number of comparison feedback required by DOPI. when directly leveraging the BT model, but also guaranteed with a bounded error (Section 3.2) Inspired by implicit exploration (Tin) et al. 2020), we further construct a biased overestimated preference estimator based on the inferred preference to further encourage exploration, which also benefits the regret characterization.
Third, to handle the instantaneous constraint in PREF-RMAB, we develop low-complexity index policy (Section 3.3 for the DM to make decisions. Specifically, we first solve a relaxed problem, which turns out to be a linear programming (LP) in terms of occupancy measures, rather than PREF- RMAB itself. Our key insight here is that we can define the objective of the LP for PREF- RMAB in terms of preference feedback directly. DOPL can therefore construct an index policy on top of
2

---

Published as a conference paper at ICLR 2025
the solutions the LP. This is another key difference compared to the solutions (Wiittle 1988 Larrañaga et al. 2014: Bagheri & Scaglione 2015] Verloop 2016 Zhang & Frazier 2021 to the standard RMAB, which heavily rely the scalar reward.
We prove that DOPL achieves an (((c) + I-D) )) 22N S In 4| A regret, where T is the time horizon, S is the state space, D is the ergodicity coefficient and cı are some constants (see details in Section We believe that ours is the first work to formally characterize the regret for Importantly, the two terms in this regret clearly maps to the aforementioned design of DOPL, i.e., the first term with coefficient C1 is the regret due to the online preference learning and the second term with coefficient 4B/( D) is caused by executing the direct index policy for PREF-RMAP Furthermore, despite the fact that the DM in PREF-RM preference feedback, which contains arguably less information than scalar rewards, PREF-RMAB still achieves a sublinear regret as the standard RMAB, thanks to the novel design of online preference learning and direct index policy in DOPL.
can only observe
PRELIMINARIES AND PROBLEM FORMULATION
We first provide a brief overview of the standard RMAB with scalar rewards, and then formally define the problem of RMAB with preference feedback and the online settings considered in this paper.
Notation. We use the calligraphic letter A to denote a finite set with cardinality |A]. Let a be permutation on A. and 0, be the position of element in A. We use bold letter F to denote matrix with j(, being the element of F in the i-th row and j-th column.
2.1 STANDARD RESTLESS MULTI-ARMED BANDITS WITH SCALAR REWARDS
For a standard infinite-horizon average-reward RMAB WWittle 1988), each "restless" arm n E described by unichain MDP (Puterman 1994 M2 (S, A. P rn), where S is the state space, A = {0, 1 is the binary action space, Pn lessss,d a) S x A x + [0, 1 is the transition probability of reaching state s' by taking action in state 8, and r. (s. E [0, : A - IR+ is the scalar reward associated with arm n of each state-action pair (s,a). At each time slot 1 E T (1, the DM activates B out of N arms. Arm n is "active" at time f when it is activated, i.e., A otherwise, arm n is "passive", i.c., A', = O. Let 11 be the set of all possible policies for RMAB, and π E 11 is a feasible policy, satisfying क F, + A where F, is the sigma-algebra generated by random variables (S% 4h Vn E -N h < t (Avrachenkov & Borkar 2022). Without loss of generality, we assume that only active arms yield rewards, i.e., I' (s, 0) = 0 (Akbarzadeh & Mahajan 2022 Xiong et al. 2022b), and hence for notational simplicity, we denote r. == (5,) in the rest of the paper. The objective of the DM is to maximize the long-term average reward subject to an "instantaneous constraint" that only B arms can be activated at each time slot, i.c.
7).
RMAB : max J(T) = inm Ex Σ
Σ
r
s.t. Σ =, WET. (1) REN
REll
T T
LET WEN
2.2 RESTLESS MULTI-ARMED BANDITS WITH PREFERENCE FEEDBACK
In this paper, we consider the setting where the scalar reward r/ in the standard RMAB is unobserv- able. Instead, the DM can only observe comparison feedback between any pair of the activated arms. We call this new RMAB model in the presence of preference feedbuck as PREF-RMAB.
Similar to the standard RMAB, the goal of the DM in PREF-RMAB is still to maximize the long-term average reward as in (1) by activating a subset of A C arms at each time slot l with B = WW For case of presentation, we refer to ( as the optimization problem that the DM needs to solve in PREF-RMAB in the rest of this paper. Unlike the standard RMAB, the DM only observes preference feedback in the form of the Bernoulli variable a $ ~ Ber( (a.,, oz
between arms (m, n) E A R according to the underlying preference matrix F E (0. (6.1) (|)xxxx11) The probability that arm m state s is preferred over arm n in state s is Pr(a(st $6) = 1)
'This probability measure can be extended to cases where (s, 0) of 0 by incorporating the action- dependence of operator F.
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 Online Interactions between the DM and the PREF-RMAB Environment
Require: State space S, action space A, unknown transition functions (Pn, Vn N], unknown preference matrix F, and an initialized policy n²;
1: for k 1. .... K do
2: The DM determines policy n. based on the collected preference feedback up to episode k;
3: for h = 2, HH do
4: DM activates a subset of N := {A = 1 arms under the instantaneous constraint;
5:
DM observes preference feedback by dueling any pair of arms in A through an oracle;
6:
Arm n. Yn moves to the next state 5ith+1 ~ Pa (a(- ,,Ah));;
7: DM observes states (Shhh+1, Vn};
8: end for
9:
end for
F((m - 1)]5- ast (n ((n-1)] 1)|$| + + ). We assume that the preference feedback at (s% 8%) is drawn
according to the widely-used Bradley-Terry (BT) model (Bradley & Terry 1952). satisfying
exp(rm (s)x))
F. F. (st F((m 1)|5| Jst. (n 1)|5| + o.
(2)
exp(Im (stm)) ) exp(rn(s()))
Hence, the block matrix F. E [IS) represents the preference between a pair of arms (m, n) over all [8] states. The preference matrix F of all arms N over all states S can then be expressed compactly terms of F. For ease of presentation, we relegate the full expression of to Appendix C.2 along with toy example for illustration.
2.3 ONLINE SETTING AND LEARNING REGRET
We focus on the online PREE-RMAB setting, where the underlying dynamics (i.e., P.) of each arm and the preference matrix F are unknown to the DM. The interaction between the DM and the CREF-RMAB environment is presented in Algorithm]] [ The DM repeatedly interacts with N arms in PREF-RMAB in episodic manner. The time horizon T is divided into K episodes and each episode consists H decision epochs, i.e., T = KH. Let TH == H(k 1) + 1 be the starting time of episode k, and hence SR. S Vn. At Tk. the DM determines a policy π and executes this policy for each decision epoch h in this episode. Specifically, at decision epoch h, the DM activates a subset of A arms according to π (- Yn}) under the instantaneous constraint, i.e., Ar : {n A = 1, Σ A = B, vn E N/. The DM then observes a preference feedback between different pairs arms in A/h through comparison oracle. Each arm moves to the next state Sk.h+1 sampled from (.,.-Sk h).
Remark 1. direct application of BT model to PREF-RMAY requires the DM to duel any pair of arms in Nh, leading complexity of ( Although B < N holds for many aforementioned RMAB applications, this amount of feedback may be impractical. A key contribution this paper is that we develop novel "preference inference" (Step 3 in Section 3.2), with which our DOPL only requires B- comparisons at each decision epoch. More details are discussed in Section
The goal of the DM is to minimize the learning regret, defined by " T) - [(
Reg((n ) (
where opt T') is the expected total rewards achieved by the offline optimal policy opt via solving {1) when the scalar rewards are observed by the DM, and [( Jk= T") is the expected total rewards achieved by the online policies ( K 1k=1 when the DM in PREF-RMAB can only observe preference feedback defined in (2).
K :
3 DIRECT ONLINE PREFERENCE LEARNING FOR PREF-RMAB
In this section, we show that it is possible to design an efficient RL algorithm that can efficiently explore the unknown environment, adaptively collect preference data in an online manner, and directly
Since finding the offline optimal policy for RMAB or PREF- PREF-RMAB is intractable and inspired by existing RMAB literature (Wang et al. 2020 Xiong et al. 2022b Wang al. (023). we characterize the regret with respect the offline index policy to in the presence of preference feedback.
4

---

Published as a conference paper at ICLR 2025
leverage the preference feedback for the computationally intractable PREF-RMAB Specifically, we leverage the popular UCRL-based algorithm (Jaksch et al., (010)) for the online PREE- RMAB setting, and develop episodic RL algorithm named DOPL summarized in Algorithm 2 There are three key components in DOPL: (1) maintaining a confidence set of the transition functions to transition functions; (2) online preference learning with comparison
deal with the unknown feedback by dueling arms to deal with unknown preference model; and (3) designing low-complexity index policy that directly leverages the preference feedback for decision-mann -makin ensure that the instantaneous constraint of PREF-RMAB is satisfied in each decision epoch.
Algorithm 2 DOPL: Direct Online Preference Learning for
Require: Initialize (s, a) O, and (s 1/ Vn s, S.a A; the preference matrix F' with all elements initialized to be 0.5; an initialized policy x²; 1: for == 1, K do
2: Execute n* and construct the set of plausible transition kernels (8, () according to (4)
3: Update the preferences matrix F+++1 according to Algorithm
4: Construct direct index policy x+41 from preference feedback by solving 12
5:
end for
Representing Scalar Rewards in terms of Preference Feedback. Before presenting the three key components DOPL, one key observation this paper is that we can represent scalar rewards in terms of preference feedback for PREF-RMAB. Proposition 1. The underlying scalar reward Tn (s) associated with arm n in state s expressed as
(H.0..
+ In 1- --FA(o,,0s.)
where * is "reference" arm, 8, is a "reference" state, and t is the block matrix of preference between the reference arm * and the arm n as defined in (2).
Remark 2. Proposition 7 Aindicates that the scalar reward of arm n state s can be expressed in terms of (i) the scalar reward of the reference arm in reference state s.. and (ii) the preference feedback between arm n and the reference arm *, which is drawn from the underlying BT model as in 2 For simplicity, define the "preferenceereffernee"" term Qn(x) = In (........) that the reference arm and reference state 8, can be any in N and any state in S, but they will remain fixed in the system once selected. We will provide insights on how to select them in practice in our experimental evaluations Section [ More importantly, as we will show in Lemma) 3 the objective of PREF-RMAB can be directly expressed in terms of preference feedback and is regardless of the sealar reward r. (s.) associated with the reference arm and the reference state.
1=F. Note
Proposition 2. Since (s) E [0, 1),1,,s,,, Qn (8) is monotonically increasing in F; O..) and bounded as Qn(s) E [-1,
Remark 3. Similar to the scalar reward rn (s) in standard RMAB, Propositions 7 and indicate
that the preference of arm n in state s in PREF-RMAB is well represented by (n) Innuitively, the higher the probability (i.e., (a,a,, Ta.) ) as defined in (2) arm in state is preferred over the reference arm * and reference state 8,, the larger the value of Q (8) will be.
3.1 CONFIDENCE SETS FOR TRANSITION FUNCTION
Since the true transition functions Pn, Vn N are unknown to the DM, we maintain confidence sets via past sample trajectories. Specifically, DOPL maintains two counts for each arm n. Let - a) the number of visits to state-action pairs (s, a) until тıe and 2 z (s, a, 8') be the number of transitions from to s' under action DOPL updates these two counts as follows:
(s, a) - (s,a) + Σim 1(St.h
-H
A a), and (s,
a, s')
2t,1(s,a,s))
Σ# ( (St.++1 s'1Stt 8, A = a), v(s,a, a 8') E S x A x S. DOPL estimates the true 2 (e.0,,') transition function by the corresponding empirical average as: (s = max (s.a).1)" then defines confidence sets at episode k
and
(s, == (s' (ss'sss,))) ss, : (s (s'|s,0) - p/ S (s)
(4)
5

---

Published as a conference paper at ICLR 2025
where the confidence width (8, a) max m (ssa)).]
log
[1S]LAIN((-I) is built according
to the Hoeffding inequality (Hoeffding. 1994) with E (0,1).
Lemma 1. With probability least 1 2e, the true transition functionn are within the confidence sets, i.e,, Pa E Ph, Vn, k.
3.2 ONLINE PREFERENCE LEARNING
From Prop 2 the preference- reference term Qn) In F. (o..))))
I=F;(o,,...)) relies on the reference arm and reference state s.. Hence, to estimate the preference of arm in state or the value of Qn(s) DOPL only needs learn one specific column of the preference matrix F, i.e., F(: (+- (+-1)[S []][S++ + o.s) ). This corresponds to the preference between the reference state s. of reference arm with any arm W in any state s S. Since the pairwise preference feedback is a Bernoulli random variable, and the probability of the random variable being 1 is stored in preference matrix F, an intuitive way to estimate F with empirical dueling samples. Our online preference learning consists of four steps detailed as follows and the pseudocode is summarized in Algorithm 3 in Appendix C33
Step 1: Pairwise Comparison. At each decision epoch h in episode k, the DM observes pairwise comparison feedback from all pairs out of the B activated arms. Let (sy(s,, 83) be the total number
of comparisons between arm i at state 8; and arm j at state 8, up to episode kt and W W (81, 8,) be the number of times when arm at state 8; is preferred over arm at state 8j. DOPL updates these two counts incrementally whenever there a comparison between the two arms at each decision epoch.
Remark 4. Since the preference matrices F and FT are complementary, i.e., F + FT 1 sixNisi and their diagonal elements are all 0.5, we only need to learn either the upper triangular part or the lower triangular part of F. Therefore, we only count City (1,(8188) and W (8;;88)) for arm at state s; and arm j at state Sj. while Cjt, ($3,, si) and (3
13, 81) are not needed.
Step 2:
Empirical Preference Estimation. At Tk+1, DOPL estimates the true preference between W ((s..s))
arm state 8; and arm j in state 8j by the empirical average as: fJ (Os,,
Despite that this is an unbiased estimation of (o Te, ), key limitation of this empirical estimate is that its success requires DOPL to activate any arm in any state "very often". Unfortunately, this may not hold true since some arms in some states may not be favored by the DM. In particular, as discussed above, DOPL only needs to estimate the preference between the reference state 8, of reference arm * with any other arms' states. This means that the success of the above empirical estimate requires DOPL to activate the reference arm * and reference state frequently, which may not be possible in practice. As a result, the preference-reference term Qn.(s) may be not updated for long time due the preference feedback model in Section 2.2 making DOPL of low efficiency.
Step 3: Preference Inference. To address the above limitation, one contribution in this work is to show that although some arms may not be visited frequently, of its preference via the other arms' empirical preference estimations.
still infer the empirical average
Lemma 2. Given the empirical preference estimations F(jJi)) F() and (j, of F() in the preference matrix F, Vj. E SN) if their estimations satisfy [F( F(j (1)) S 51 and [F (j.jz2 F(j.jn f2)] S 82 with probability at least 1 2e, where ô1, d2, e are some constants, then we can infer the value F(i.h2) as
(1- ((. Fi.,ee)
End Fnd
(5)
(1 (I. + (1 F(..2))
In addition, we have | (11 - F(11522) S ((61+55) with L = 1.3 being a Lipschitz constant.
Remark 5. Lemma 2 indicates that for a fixed reference arm * and reference state s., even though DOPL may not visit arm in state frequently (i.e., the empirical estimation in Step 2 may not be accurate), we can still infer its preference (o G2.) once we have an "accurate" " empirical preference estimation of F* (asm ) and F (O a.m) for any arm m. and states Sa, Sm. More importantly, the inference error can be bounded by some constants L, 8, 82. Thanks to this novel preference inference design, our DOPL only needy B comparison feedback in each decision
6

---

Published as a conference paper at ICLR 2025
epoch, rather than (B²²) when directly applying the BT model to PREE- (see Remark 7 An illustrative toy example for the preference inference is presented in Appendix C.4
Given the empirical preference estimation x (as,; F
from Step and the corresponding inferred preference 1y,.++1,iff (o J..) from Step 3, we define the corresponding errors as o5.... ...
and 6inn s..... respectively, via Hoeffding inequality. Specifically, 6s..s. is the confidence interval for empirical preference estimation between arm n in state 8,, and the reference arm reference state 8x, is the inferred confidence interval when direct comparison data which is determined as in (4). e between 8n and 8, is sufficiently available, which is determined in Lemma 2 DOPL selects the one with a smaller error as the desired estimated preference, and denote it as Fz F (.... x..)
Step 4: Overestimation for Exploration. We further leverage the idea of implicit exploration (Jin et al. 2020 to further encourage exploration. Specifically, we increase " (ax.. xx.) with bonus term ā to obtain biased estimator, denoted as Fi T..) = F; (o... o.,) + 8, where 5 min(6"., (0... 6.....) ) is the confidence level over F, (",,,, :..) with probability least 1 - 2e. It is clear that (r, Ts.) is overestimating F (o T..) with high probability. Using overestimation can be viewed as optimism principle to encourage exploration, and is beneficial for the regret characterization (Jin et al. 2020).
max J(x) is known that solving the PREF- RMAB in (I) is computationally in- tractable even in the offline setting with scalar reward feedback (Papadim: iitiiou & Tsitsiklis 1994). To tackle this challenge and inspired by Whittle (Whittle 1988). we first relax the in- stantaneous constraint, i.e., the constraint is satisfied on average rather than in each decision epoch. It turns out (Verloop, 2016) Zhang & Frazier 2021 Xiong et al., (022b) that this relaxed problem can be equivalently transformed into I.P 46)-(9 terms of occupancy measures (Altman 1999). Specifically, the occupancy measure Pn (s, a) limr
ΣΣΣ
E
an)(sa)rr((
(6)
3.3 DIRECT INDEX POLICY
BEN &ES AEA
s.t. ΣEΣ E
apn (s,
(7)
nEN sES aEA
as)
pals' a') d') Vn, (8)
ΣΣ Mn (s Vn, 8,a, aESaEA
7 E Σ. 11ss = 8, s,a,, a) is the expected number of visits to each state-action pair (s,a) of arm and n² of a stationary policy π for N controlled infinite-horizon MDPs is defined as 1rx = (s,(8, a) : Vn, 8, a). It is obvious that the occupancy measure satisfies E(.,)) (n, 1. and hence Pn, Vn N is probability measure. Unfortunately, we cannot solve this LP since cannot directly observe the scalar rewards rn (s), Vn, s in PREE-RMAB To address this challenge, we first show that we can equivalently transform the LP (6)-9)) into a new LP in terms of preference feedback for PREF-RMAB.
Deriving the LP's Objective. With Lemma] and Lemma 2 our second key observation is that the objective of the I.P for PREF-RMAB can be expressed in preference feedback directly.
Lemma 3. The objective (xx) of the LP (6)-19) can be equivalently transformed into the following objective JNOPI.(M) (T)) in terms of preference feedback:
(T) == max
ΣΣΣ nEN BES aE.A
(s).
(10)
Proof. According to Lemma
1 the objective ((T) the LP ( be rewritten as
J(z) :- max 1
ΣΣΣ (n sES
ΣΣΣ nEA dES
Mn (s)
(11)
Due to the fact that the occupancy measure a probability measure, i.e., Eves we have that Enex Eees E.eA pn (s, a)r, (s.) = Nr. (s.), which is independent of policy ,t Therefore, the objective ((T) (II only depends on the first term. We denote as (DDPL(T)) which purely depends on the preference teedback drawn from the underlying BT model in (
=)
O
Remark 6. Lemma I indicates that we can relax the PREF- RMAB and then equivalently transform it into new I. in terms of occupancy measures and the preference feedback directly.
7

---

Published as a conference paper at ICLR 2025
Designing Direct Index Policy for
Due to the lack of knowledge of the true transition functions (i.e., (. s, a), vs, a. n) associated with each arm n, and the true preference (s.s), Vn, s, we further rewrite the new LP with objective (TO) as an extended LP (ELP) by leveraging the (s a) a) (s, a) to express the confidence intervals of transition probabilities (see Section 3.1 Together with the estimated preference-reference term Qh Vs, (see Section
state-action-state occupancy measure (n a, 8
3.2). the DM ends up to solve an ELP each episode
w arg max w
(LP(PP a), (s),
(12)
where wh far (s, a, s'), Vn E M]. We present more details about this ELP in Appendix C. However, the optimal solution w ~ to (12) is not always feasible for PREF- REEE-RMABB due to the fact that the instantaneous constraint in PREF-RMAB must be satisfied in each decision epoch rather than on the average sense as in this ELP. Inspired by Verloop (2016); Zhang & Frazier (2021); I: Xiong et al. (2022b), we further construct an index policy on top of " that is feasible for PREF- RMAB. Specifically, the index assigned to arm in state s
at time t is defined
Yn'es wh (a,1,s")
as I+ EnEA.'es (s.a,,"" We call this the direct index since it is constructed by solving
LP in preference feedhack directly. We then rank all arms according to their direct indices in non-increate -on-increasing order, and activate the set of B highest indexed arms at each decision epoch. We denote the resultant direct index policy as n* and execute in episode k. Asymptotic optimality of this index policy relies on the existence of uniform global attractor (Gast et al. 2024). a standard assumption in the RMAB literature.
THEORETICAL GUARANTEE
Now provide the performance guarantee for DOPL, which is formally stated in Theorem Theorem 1. With probability at least - 2e, the regret of DOPL satisfies
Reg(T) < =ō ((20 220 +
4B I
22NTS In 4[S|AANT
V
(13)
where C1 =: maxi.j FO.N F(..])) is a constant, and D is the ergodicity coefficient (see the detailed definition in Appendix E.3
Remark 7. The regret contains two terms. The first term with coefficient 01 is the regret due to the online preference learning (Section 3.2) The second term with coefficient 4B/(1- D) is caused by executing the direct index policy for PREE-RMAB (to satisfy the instantaneous constraint) (Section 3.3 Clearly, the regret of DOPL is in the order of In which matches that of the standard RMAB with scalar rewards Ortner et al.) 2012 Wang al. 2020 Xiong al. 2022a).. However, comparing to the standard RMAB with scalar rewards, our PREF-RMAB is harder problem in which the DM can only observe preference feedback, which arguably contains less information. This challenging setting thus requires us to develop an effective online preference learning algorithm to handle preference feedback, as well as a new index policy that can directly leverage the preference feedback to make decisions.
Proof Sketch. Compared to the standard RMAB, the key challenges of our DOPI. for PREF-RMAB come from the online preference learning and the direct index policy to deal with preference feedhack. To address these challenges, we first decompose the regret of DOPL correspondingly.
Lemma 4. Let { Vk} be the direct index policy executed in each episode with transition functions drawn from the confidence sets defined in ( and the preference overestimated by Algorithm 3 Let J( Vk), (F* vk), T) and J{ , Vk), with overestimated preference [F'y and the true preference F, respectively. The regret of DOPL can be decomposed and bounded as
F,T) be the total rewards achieved by policy ( Vk}
Reg({a* 1k=1 T) < J[{ak, VkJ. F VKJ, T) J(F F,T)
Term
J(IT", VkJ, F. T) J(L VkJ.F.T)
(14)
Terma
8

---

Published as a conference paper at ICLR 2025
Specifically, Termy is the regret due to the preference estimation error between the true preference F and estimated ones F*, Ak (Section 3.2p. Terma is the performance gap between the policy { vk) in the optimistic plausible MDP and the learned index policy {** Vk} for the true MDP (Section 3.3 The inequality holds due the optimism brought by upper confidence ball search (Section 3.1 and the preference overestimation (Section (.2). and the fact that the LP in
provides an upper
bound for the optimal solution of PREF- RERE-RMABBB in ① (Section 3.3
Bounding Terma. We first bound Termi, i.e., the regret caused by online preference learning.
Lemma 5. With probability 2e, we have Term: 2c1 2N In 4|8|AANNT
Bounding Term requires us first to characterize the impact on the preference-reference term Qn(s), Vn, made by the preference estimation error, and then to bound the inner product Ek=1 EN (w - with w and Q being the vectors containing (w a, 8'), Vs, 8') and VsJ. respectively.
Bounding Term2. Next we bound Terma, i.e., the regret due to the direct index policy.
Lemma 6. With probability 2e, we have Terms S 2N S 4[S||AINT
Bounding Terma requires us to decompose the regret into each episode. The key is to leverage the ergodicity the underlying MDP of restless arms and bound the gap between stationary distribution and the true number of visits of each state-action pair, related to the instantaneous constraint B.
Reward
Regret
Curnulative negret
Episadic Resward
630
300000
200000
100000
550
1500 2500
3500 3000
4000
500
1500
2000
3000 3500
Episodes
Episodes
RANDOM
MLE, WIBQL
MLE_QWIC
MLE LP
DOPL
ORACLE
Figure 1: Comparisons of episodic reward and cumulative regret under App-Marketing environment.
EXPERIMENTS
In this section, we evaluate the efficacy of DOPL for PREF-RMAB via real-world applications. The experiment code is available at http::////gghhabb..co//////--///
Baselines. We consider three classes of baselines: (i) Oracle, which is the optimal index policy (Ver- loop 2016 Zhang & Frazier 2021), derived from solving 6 6 using full knowledge of the reward function and transition kernels, serving performance upper bound.
(ii) MLE based algorithms, which employ maximum likelihood estimation (MLE) under the BT model to estimate rewards and then apply different learning algorithms, including MLE WIBQL that utilizes a Whittle index-based Q-learning algorithm (Avrachenkov & Borkar 2022). MLE LP that estimates transition kernels from observed state transitions and solves the linear program (6)-9 for index policy derivation, and MLE_QWIC that integrates MLE with the Q-learning algorithm from Fu et al. (2019). (iii) RANDOM, in which the DM activates each arm randomly, without preference feedback.
Synthetic Environment. We consider a synthetic environment named App Marketing that mimics user engagement and retention dynamics. A detailed description provided Appendix B.] and the transition kernel and latent reward function specifications provided in Appendix F.1
Real-world Environments. We consider two real-workd applications for PREE-RMAB (i) Continu- Positive Airway Pressure (CPAP) Therapy. The CPAP environment (Herlihy al. 2023 Li & Varakantham 2022 Wang et al.] 2024a) addresses patient adherence to treatment for obstructive sleep apnea. A detailed description provided in Appendices B.2 and F2 The objective is maximize

---

Published as a conference paper at ICLR 2025
Reward
Regret
1800
Episodic Reward
1590
Cumulative Regre!
150000
100000
1450
50000
1400
6
200
400
600
800 Episodes
1000
1200
1400
1600
0
200
400
600
600 Episodes
1000
1200
1406
1600
RANDOM
MLE WIBQL
MLE LWIIII
MLE LP
DOPL
ORACLE
Figure 2: Comparisons of episodic reward and cumulative regret under CPAP environment.
Reward
Regret
60
Cumulative Regret
200000
150000
Episedic
550
100000
45
40
20000
5000
Episodes
Episodes
RANDOM
MLE_ WIBQL
MLE_QWIC
MLE
DOPL
ORACLE
Figure Comparisons of episodic reward and cumulative regret under ARMMAN environment.
cumulative patient adherence and we measure this by tracking these latent rewards. (ii) Maternal Healthcare. ARMMAN (Biswas al., 202T Killian al. (022) addresses maternal healthcare intervention problem via a binary-action RMAB. For more details refer Appendices B.3 and F3
(left), DOPL significantly outperforms all considered baselines and reaches close to the oracle. In addition, DOPL much more computationally efficient since it directly leverage the preference feedback for decision making, while the considered baselines require a reward estimation step via MIE in the presence of preference feedback, which can be computationally expensive. Finally, our DOPL yields sublinear regret as illustrated in Figures 2 (right), consistent with our theoretical analysis (Theorem T while none of these baselines yield a sublinear regret the presence of preference feedback.
Observations. As shown in Figures
CONCLUSION
In this paper, we presented novel restless bandits model, dubbed as PREF-RMAB, in the presence of preference feedback, and proposed DOPL, an episodic reinforcement learning algorithm that can efficiently explore the unknown environment, adaptively collect preference data in online manner, and directly leverage the preference feedback for decision-makinn We proved that DOPL achieves sublinear regret and demonstrated its utility via experiments real-world applications.
LIMITATIONS
While the proposed study on the restless multi- bandits (RMAB) introduces novel approach by incorporating preference feedback instead of scalar rewards, it has several limitations. The shift to preference feedback, although potentially more accessible than rewards, inherently provides less information, which implies that greater amounts of data are needed for online training. Most existing RL algorithms and preference learning methods, such as RLHF and DPO, are typically designed for offline settings with pre-collected datasets, whereas the proposed RMAB with preference feedback (PREF-RAM RMAB) model operates an online context. The empirical estimation of preferences, crucial for the proposed Direct Online Preference Learning (DOPL) algorithm, requires frequent activation of arms in various states for online comparisons, which would require the development of a platform for exercising options and collecting feedback from users the algorithms learn.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Research was funded in part by grants NSF CNS 2148309, 2312978 and 2337914. All all opinions expressed are those of the authors, and need not represent those of the sponsoring agencies
REFERENCES
Nima Akbarzadeh and Aditya Mahajan. On learning whittle index policy for restless bandits with scalable regret. arXiv preprint drXiv:220..33663, 2022.
Eitan Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
Aristotle Arapostathis, Vivek Borkar, Emmanuel Semandez--Gucheramne Mrinal Ghosh, and Steven Marcus. Discrete-time controlled markov processes with average cost criterion: A survey. SIAM Journal on Control and Optimization, 31(2):822-344 1993.
Konstantin Avrachenkov and Vivek S Borkar. Whittle index based q-learning for restless bandits with average reward. Automatica, 139:110186, 2022.
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 4447-4455. PMLR, 2024.
Saeed Bagheri and Anna Scaglione. The restless multi armed bandit formulation of the cognitive compressive sensing problem. IEEE Transactions on Signal Processing. 63(5): 183-113111111 1198,119,, 2015.
Dimitris Bertsimas and José Niño-Mora. Restless Bandits, Linear Programming Relaxations, and Primal-Dual Index Heuristic. Operations Research, 48(1):80-90, 2000.
Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, and Milind Tambe. Learn to intervene: An adaptive learning policy for restless bandits in application to preventive healthcare. Proc. of IJCAI, 2021.
Vivek Borkar, K Ravikumar, and Krishnakant Saboo. An index policy for dynamic pricing in cloud computing under price commitments. Applicationes Mathematicae, 44:215-245, 2017.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4) 1952.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations reinforcement learning from human feedback. arXiv preprint vrXiv:2307.15217, 2023.
Gongpu Chen, Soung Chang Liew, and Deniz Gunduz. Gino-q: Learning asymptotically optimal index policy for restless multi-armed bandits. arXiv preprint arXiv:2408. 09882, 2024.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in-the-loop Provably efficient sefference-bssele reinforcement learning with general function approximation. In International Conference on Machine Learning, pp. 3773-3793, PMLR, 2022.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Kobi Cohen, Qing Zhao, and Anna Scaglione. Restless multi-armed bandits under time-varying activation constraints for dynamic spectrum access. 2014 48th Asilomar Conference on Signals, Systems and Computers, pp. 1575-1578. IEEE, 2014.
Yihan Du, Anna Winnicki, Gal Dalal, Shie Mannor, and R Srikant. Exploration- driven policy opti- mization rlhf: Theoretical insights on efficient data utilization. arXiv preprint arXiv:2402. 10342, 2024.
11

---

Published as a conference paper at ICLR 2025
Miroslav Dudik, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pp. 563-587. PMLR, 2015.
Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01.36, 2024.
Jing Fu, Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards q-learning the whittle index for restless bandits. In 20/9 Australian & New Zealand Control Conference (ANZCC), pp. 249-254.
IEEE, 2019.
Nicolas Gast, Bruno Gaujal, and Chen Yan. Linear program-based policies for restless bandits: Necessary and sufficient conditions for (exponentially fast) asymptotic optimality. Mathematics of Operations Research, 49(4):2468-22) 2491, 2024.
Christine Herlihy, Aviva Prins, Aravind Srinivasan, and John P Dickerson. Planning fairly allocate: Probabilistic fairness in the restless bandit setting. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 732-740, 2023.
Wassily Hoeffding. Prohability Inequalities for Sums of Bounded Random Variables. In The Collected Works of Wassily Hoeffding, pp. 409-426, Springer, 1994.
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. Advances neural information processing systems, 31, 2018.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-Optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Young Hun Jung and Ambuj Tewari. Regret bounds for thompson sampling in episodic restless bandit problems. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Jackson A Killian, Andrew Perrault, and Milind Tambe. Beyond" To Act Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits. In Proc.of AAMAS, 2021.
Jackson A Killian, Lily Xu, Arpita Biswas, and Milind Tambe, Restless and uncertain: Robust policies for restless bandits via deep multi-agent reinforcement learning. In Uncertainty in Artificial Intelligence, pp. 990-1000. PMLR, 2022.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pp. 1141-1154. PMLR, 2015.
Maialen Larrañaga, Urtzi Ayesta, and Ina Maria Verloop. Index Policies for with Convex Holding Cost and Abandonments. In Proc. of ACM Sigmetrics, 2014.
Queue
Dexun Li and Pradeep Varakantham. Towards soft fairness in restless multi-armed bandits. arXiv preprint 1xXiv:2207.133433 2022.
Aditya Mate, Jackson Killian, Haifeng Xu, Andrew Perrault, and Milind Tambe. Collapsing bandits and their application to public health intervention. Advances in Neural Information Processing Systems (NeurIPS), 33:15639-156500 2020.
Aditya Mate, Andrew Perrault, and Milind Tambe. Risk-Aware Interventions in Public Health:
Planning with Restless Multi-Armed Bandits. In Proc.of AAMAS, 2021.
Rahul Meshram, Aditya Gopalan, and D Manjunath. Optimal recommendation to users that react: Online learning for a class of pomdps. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 7210-7215. IEEE, 2016.
12

---

Published as a conference paper at ICLR 2025
Khaled Nakhleh, Santosh Ganji, Ping- Chun Hsieh, I Hou, Srinivas Shakkottai, et al. Neurwin: Neural whittle index network for restless bandits via deep rl. Advances in Neural Information Processing Systems (NeurIPS), 34:828-888 839, 2021.
Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret Bounds for Restless Markov Bandits. In Proc. of Algorithmic Learning Theory, 2012.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback, Advances in neural information processing systems (NeurIPS), 35:27730-27744, 2022.
Christos Papadimitriou and John N Tsitsiklis. The Complexity Optimal Queueing Network Control. In Proc. of IEEE Conference on Structure in Complexity Theory, 1994.
Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference on Machine Learning, pp. 1901 1-19026. PMLR, 2022.
Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pp- 968-994. PMLR, 2022.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 6263-6289, PMLR, 2023.
Yunhao Tang, Zhaohan Daniel Guo, Zeyu Zheng, Daniele Calandriello, Rémi Munos, Mark Rowland, Pierre Harvey Richemond, Michal Valko, Bernardo Ávila Pires, and Bilal Piot. Generalized preference optimization: A unified approach to offline alignment. arXiv preprint arXiv:2402.05749 2024.
Cem Tekin and Mingyan Liu. Adaptive Learning of Uncontrolled Restless Bandits with Logarithmic Regret. In Proc. of Allerion, 2011.
Ina Maria Verloop. Asymptotically Optimal Priority Policies for Indexable and Nonindexable Restless Bandits. The Annals of Applied Probability, 26(4):1947-1995, 2016.
Kai Wang, Lily Xu, Aparna Taneja, and Milind Tambe. Optimistic whittle index policy: Online learning for restless bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 10131-10139, 2023.
Shufan Wang, Guojun Xiong, and Jian Li. Online restless faimeess constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15616-15624, 2024a.
bandits with long-term
Siwei Wang, Longbo Huang, and John Lui. Restless-uch ucb, efficient and low-complexity algorithm for online restless bandits. Advances in Neural Information Processing Systems (NeurIPS), 33: 11878-1 1889, 2020.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rl? a theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024b.
Peter Whittle. Restless Bandits: Activity Allocation in A Changing World. Journal of applied probability, pp. 287-298, 1988.
13

---

Published as a conference paper at ICLR 2025
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-45 2017.
Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. Advances neural information processing systems, 29, 2016.
Guojun Xiong and Jian Li. Finite-time analysis of whittle index based q-learning for restless multi- armed bandits with neural network function approximation. Advances in Neural Information Processing Systems, 36:29048-22 29073,9973 2023.
Guojun Xiong, Jian Li, and Rahul Singh. Reinforcement learning augmented asymptotically optimal index policy for unite-horizon restless bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8726 8734, 2022a.
Guojun Xiong, Shufan Wang, and Jian Li. Learning infinite-horizon average-reward restless multi- action bandits via index awareness. Advances in Neural Information Processing Systems, 35: 17911-17925, 2022b.
Guojun Xiong, Shufan Wang, Gang Yan, and Jian Li. Reinforcement learning for dynamic dimen- sioning of cloud caches: A restless bandit approach. JEEE/ACM Transactions on Networking, 31 (5):2147-2161 2023a.
Wei Xiong. Hanze Dong, Chenlu Yc, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl- constraint. In ICLR 2024 Workshop Mathematical and Empirical Understanding of Foundation Models, 2023b.
Zhe Yu, Yunjian Xu, and Lang Tong. Deadline Scheduling Restless Bandits. IEEE Transactions on Automatic Control, 63(8):2343-253) 2018.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits 2012.
problem. Journal Computer and System Sciences,
Xiangyu Zhang and Peter Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv preprint arXiv:2107.11911 2021.
Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Saleh, and Peter J Liu. Slic-hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305. 2023.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In International Conference on Machine Learning (ICML), pp. 43037-43067. PMLR, 2023.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint ar arxiv: http::99900089993. 2019.
A RELATED WORK
Dueling Bandit. Dueling bandit generalizes the classic multi-armed bandit problem by pulling two arms to duel time and only receives the preference feedback (uue al., 2012). Introduced by Yue et al. (2012), the initial algorithms such as Interleaved Filter laid the groundwork for this field. Subsequent developments include the Double Thompson Sampling (DTS) (Wu & Liu 2016). which improved empirical performance and robustness. Theoretical advancements have been made in Komiyama al. (2015) which analyzed regret bounds. Dueling bandit has been extensively studied, under various objectives and generalizations, and applied to various applications (see Saha & Gaillard (2022) for detailed discussions). Recently, [Saha Gaillard (2022) made notable contributions by proposing reduction from dueling bandits to multi-ane armed bandits. enabling optimal performance in both stochastic and adversarial environments. Their algorithm achieves an optimal regret bound against the Condorcet-wing winner benchmark and demonstrates robustness under adversarially corrupted
14

---

Published as a conference paper at ICLR 2025
preferences. Another significant work Saha & Krishnamurthy (2022) addresses the contextual dueling bandit problem, focusing on regret minimization under realizabilityy Their algorithm achieves optimal regret rates for a new performance measure called best response regret, resolving an open problem regarding oracle-efficient, regret-optimal algorithms for contextual dueling bandits posed by [Dudik] et al. (2015). These advancements highlight the progress in dueling bandit research.
Reinforcement Learning from Human Feedback. Reinforcement Learning from Human Feed- back (RLHF) integrates human preferences into the RL framework to guide the agent's learning process, overcoming the challenge of specifying appropriate reward functions. A pioneering work by Christiano et al. (2017) demonstrated that using human comparisons to train agents significantly improved their performance in complex tasks. Building on this, Ibarz et al. (2018) combined demon- strations with human feedback, accelerating the learning process and reducing the amount of required feedback. Most existing RLHF work (Chen et al., 2022 /Zhu et al.) [003] Du et al., (024) typically assumes a linear reward function, i.e., there exists a known feature mapping to specify the feature vectors of state-action pairs. Later on, a line of work proposed algorithms that directly learn from
preferences without explicit reward modeling (Ratailov et al. 2024. Zhao et al. 2023 Azar et al. 2024, Ethayarajh et al. 2024; Tang et al., 2024). Need to mention that most of the latest RLHF and DPO based methods are considered offline and provided with a given and pre-collected human preference (and transition) dataset, leading to the problem of overoptimization (Xiong al.. 2023b).
Recently, (Saha et al. (023) proposed Dueling RI., which utilizes binary preferences over trajectory pairs to guide learning, providing robust performance in environments with non-Markovian rewards and unknown transition dynamics. These advancements highlight the potential of RLHF in creating
more adaptable and user-aligned reinforcement learning systems (Rafailov et al. 2024). There is also a line of research from the theoretical perspective of RLHF, showing the effciincy of RLHF comparable conventional RL. Please see WWan et al. (2024b) for detailed discussions.
Restless Multi-Armed Bandits. RMAB was first introduced in Whittle (1988, and has been widely studied, see Xiong et al. (2022)) and references therein. In particular, RI. algorithms have been proposed for RMAB with unknown transitions. Colored-UCRI.2 is the saat--of-hh--an method for online RMAB with ÖVVTIT)) regret. To address the exponential computational complexity of colored-UCRL2, low-complexity RL algorithms have been developed. For example. Wang et al. (2020) proposed generative model-based algorithm with ((T2/3) regret, and Xiong et al. (2022a b) designed index-aware RL algorithms for both lnite-horizon and infinite-horizon average reward settings with Ö(vT) regret. However, the aforementioned existing literature on RMAB focus on the stochastic setting, where the reward functions are stochastically sampled from a fixed distribution, either known unknown, and at each decision epoch, the reward is observed by the decision marker. To our best knowledge, this work is the first to study RMAB in the presence of preference feedback, where the decision marker only observes pairwise preference signals.
B MOTIVATING EXAMPLES FOR PREF-RMAB
In the following, we provide some motivating examples that can be modeled as a PREF-RMAB problem, i.e., the RMAB problem in the presence of preference feedback.
B.1 APP MARKETING
Imagine you're a marketing manager for a popular mobile app that offers various features to users. You'te re tasked with the job of maximizing user engagement and retention. Each day, you have a limited budget to send personalized push notifications or in-app messages to a subset of users to boost engagement and retention. Due to resource constraints, you can only target a fixed number of users daily.
Scenario:
State Modelling: Each user is modeled "restless" arm whose engagement state evolves over time based on whether they receive targeted marketing efforts.
81 User at risk of churn-has not used the app in over a month.
82 Low engagement-has not used the app in over a week.
uses 83 Moderately engaged-use uses the app a few times week.
15

---

Published as a conference paper at ICLR 2025
$4 Highly engaged uses the app daily, interacts with multiple features.
Preference Feedack: Instead of directly measuring the exact engagement metrics (which can be noisy delayed), you obtain preference feedback by comparing the relative engagement levels among the users you targeted. For example, after sending out notifications, you observe which users opened the app, how much time they spent, how they interacted with the app features.
This preference feedback is modeled using the BT model:
exp(r<(8A))
Pr(User A engages with the app more than User B 18,88)) exp(rA(sA)) exp(ra(sB))
where rAA (SA) and (B($B) represent the latent engagement and retention potentials of Users A and based on their states.
Objective: The goal to maximize overall user engagement and retention without needing to quantify the exact contribution of each user (which can be challenging due to data privacy concerns or measurement noise). By focusing on pairwise preference feedback among the targeted users, you can iteratively improve your targeting strategy select users who are more likely to respond positively to your marketing efforts.
B.2 CPAP TREATMENT
Scenario: You are healthcare provider managing large cohort of patients diagnosed with obstruc- tive sleep apnea (OSA). The standard treatment for OSA is Continuous Positive Airway Pressure (CPAP) therapy, which requires patients to use CPAP machine during sleep every night. However, patient adherence to CPAP therapy is often low due to discomfort, inconvenience, or lack of immediate perceived benefits. With limited resources (e.g., time, staff), you can provide personalized follow-up support or interventions to only select number of patients each week to encourage adherence.
State Modelling: Each patient is modeled as "restless" arm whose adherence state evolves over time based on whether they receive follow-up support. The state space for each patient considers various factors affecting adherence:
Low Adherence Uses CPAP sporadically with short usage durations.
$2 Moderate Adherence Uses CPAP most nights but not consistently for the full duration.
$3 High Adherence- Uses CPAP every night for the recommended duration ( hours per night).
Preference Feedack: Quantifying exact adherence levels for each patient can be challenging. Instead, you obtain preference feedback by comparing relative adherence among the patients you have intervened with.
This preference feedback is modeled using the BT model:
exp(ra(8A))
Pr(Patient A is more adherent than Patient B 8A, exp(rA(sa)) exp(rB(SB))
where A)) and (s())) represent the latent adherence potentials of Patients A and B based on their current states.
Objective: The goal is to maximize overall patient adherence to CPAP therapy without needing precise adherence measurements for each individual. By focusing on pairwise preference feedback among the patients you have provided interventions to, you aim to:
Optimize Resource Allocation: Identify and support patients who more likely to improve their adherence with additional intervention.
Improve Health Outcomes: Enhance the effectiveness of CPAP therapy across the patient population by increasing overall adherence rates.
B.3 MATERNAL HEALTHCARE
Scenario:
You are collaborating with ARMMAN, a non non-govermmental organization focused on im- proving maternal and child health in underserved communities by delivering vital health information
16

---

Published as a conference paper at ICLR 2025
through mobile technology. The program involves sending automated voice calls to expecting and new mothers, providing them with timely healthcare guidance. However, due to limited resources such call center capacity and funding, you only reach out to subset of mothers each day. The challenge is to select which mothers to contact to maximize overall engagement with the program, thereby enhancing health outcomes.
State Modelling: Each mother(or benefeciary) modeled as a "restless" arm in a Markov Decision Process (MDP) with three ordered states representing their level of engagement:
81 Lost Cenii-bbenssciiaries listening to less than 5% of the content of the automated calls.
$2 Persuadable--eneffeee listening to between 5% and 50% of the content of the automated calls.
$3
beneficiaries listening more than 50% of the content of the automated calls. Having to measure and keep track of the exact engagement levels of each beneficiary can be tedious even infeasible with scale. Thus you could just rank the engagement levels among the beneficiaries you reached out to in order to get your preference feedback signal.
Preference Feedack:
This preference feedback is modeled using the BT model:
exp(ra(8A))
Pr Pr(Beneficiary A is more engaged than Beneficiary B 8B) = exp(rA(sA)) + exp(r=(sB))
where r,A (SA) and (B(SB) represent the latent engagement potentials of Beneficiaries A and B based on their states.
Objective: The goal is maximize overall beneficiary engagement and retention without needing to quantify the exact contribution of each user (which can be challenging due to data privacy concerns or measurement noise). By focusing on pairwise preference feedback among the targeted users, you can iteratively improve your targeting strategy select users who are more likely to respond positively to your marketing efforts.
B.4 SPORTS PSYCHOLOGIST
Scenario: Say you't re a sports psychologist at a top-tier football club in the premier league and in workday you can counsel at most players. You need to choose which players from the squad to counsel such that the overall team performance is maximized. Each player is modeled as a "restless" arm, whose mental and physical state evolves with time based on whether the player received counsel or not.
State Modelling: The following is one possible simplified state space definition that takes into account various factors that might affect player performance such as amount of sleep had last night, calorie intake, mental sharpness, sprint speed:
$1 Over 8 hrs of sleep; Met calorie intake level; Feeling mentally sharp; Sprint speed within 10% of personal best for the season.
$2 Less than 8 hrs of sleep; Met calorie intake level; Feeling mentally sharp; Sprint speed within 10% of personal best for the season.
$16 Less than 8 hrs of sleep; Did not meet calorie intake level; Not feeling mentally sharp; Sprint speed less than 90% of personal best for the season.
Preference Feedack: The sports psychologist can rank the players he counselled based on their performance levels on the next game/training session in order to get the preference feedback signal needed for decision making.
This preference feedback is modeled using the BT model:
exp(r.A(A))
Pr(Player A performs better than Player B s sB) exp(rA(sA)) + exp(rB(SB))
where T (s and (n(sp) represent the latent measures of how much a player contributes to team performance.
17

---

Published as a conference paper at ICLR 2025
Objective: Here the objective of maximizing team performance is attained without having to specifically identify how much each player contributed to the team performance (which can difficult thing quantify). The sports psychologist only needs to assess which player contributed more in comparison with one another to achieve the same end goal.
C MISSING DETAILS FOR THE MAIN PAPER
C.1 EXTENDED LP
The detailed formulation of ELP is provided as follows.
(s's max w
Σ
Σ
Σ
a
a, s'),a,
(s.))ESxds'E5
s.t.
Σ
Σ
Σ
aw 8,), S B,
(sa))SXAF's EEES
Σ
Σ
wh( =1, VEEN
(s.))SxAA''S
Σ
Σ a' VnE,,
(er (SS
(dTa))ESxA
w -P 10,
Σ wh
at
E, wh. (( (15)
C.2 PREFERENCE MATRIX AND EXAMPLE
In the following, we first present the detailed compact form of the preference matrix F and then provide illustrating example.
The compact form of the preference matrix F E (0, 1) is given as:
N|S]
F
F
F.N
F
F
exp(ra(s1))
exp(x((11) toxp:
F=
F
exp(ri(e(s))
exp(ri(ess)) epptraenga))eepppsseee.
which contains N x N block matrix F E S| Vm, n E N. In particular, the preference of arm m at state Sm over arm n at state 8, lies in the ((m- 1)|S] + o --th row and ((n-1(n)))) 1)]S| + ) column of F, i.e.
exp(rm((sm))
F(mm - 1)[S} + oem. (n 1)|8| )e.) exp(rm (8m) ) exp(rn(sn))
(16)
For ease understanding, we present toy example as follows.
Example 1. An illustrative example with 2 arms (i.e., N = 2) is shown in (7). where each arm has 2 states (i.e., |S] = 2) and rewards are denoted as Ti (s1), ri (82), and r2 (8) ),(22)) respectively. Given the preference matrix in 17), have reward order as (81) < <2(2s) (12)) S r2(82)-
18

---

Published as a conference paper at ICLR 2025
Note that the comparison between the same arm and the same state always results in 0.50 according to the Bradley- Terry model in (2).
(81)
ri
(82)
(2(
r2 (82)
(1)
0..0
0.30
0.33
0.24
(52
0.70
0.50
0.54
0.43
F
(17)
(8)
0.67
0.46
0.50
0.39
(8))
0.76
0.57
0.61
0.50
According to Example[] the preference of arm 2 at state 81 over the arm 1 at state 82 can be located the 3rd row and the 2nd column of F, i.e., F3, 2), where ds and 022 2.
C.3 PSEUDOCODE OF ONLINE PREFERENCE LEARNING
The pseudocode of online preference learning in Section 3.2 is presented the following algorithm. In partieular, we focus on the detailed procedures of the algorithm at the k-th episode, vk.
Algorithm 3 Online Preference Learning for the k-th Epsiode
Require: Arms set N,, confidence parameter E (0, 1), reference arm * and reference state 84; Estimating the true F;
Ensure:
1: Initialize: City (8;, 85) City (si, and Wit (8;, 85) (s;, 85), Vi,j E E 8j, 83 E S;
2: for h = 1,,,.... .. do
3: At each time step, choose B arms denoted A and perform (B 1) duels randomly;
4: for i.j E AA do do
5: Cl (,t Sj) t City (st, 8j) +
6: Observe or, over j) = 1 an over i):
7: Define (t( == I( (i over j)) and (st, + ())(s + Etmi 1, (i,j);
8: end for
9:
end for
Empirical estimation of each element in F calculated according E. (o.,,
(anee))) Cif(o)ie))
with estimation error Ösgays Vo, N, 8,, 85 E S;;
11: Select one element j from the ((* S) + as, )-th column of matrix Fnm i.e., FM (j. ((*
1)|8| + as,) )) with the smallest estimation error Infer F* 1,inf (o... o..) with F* (j. ((+ - S|
o..)) according (5) and keep the corre-
sponding inference error S..s. Vn E N 8, E S;
DOPL selects the one with smaller error as the desired estimated preference, and denote it as (r. (a......)) o..).. Vn N, 8n from the empirical estimator and the inference.
n
14: Add a bonus term as
Ft. (o.,,, Ts.)
k (a Ts.) +
min
ginl 88.8.
max (8..8. ((
In
Algorithm 3 contains the four key steps in in Section In particular, lines 2-9 in Algorithm correspond to Step Pariwise Comparison, line 10 denotes the Step 2: Empirical Preference Estimation, lines 11-13 are the realization of Step 3: Preference Inference, and line 14 is the final Step Overestimation for Exploration.
C.4 EXAMPLE OF LEMMA 2
To better understand the importance of Lemma 2 we provide the following example.
Example 2. Assume have N 5 arms (i.e., 1, 4, 5) and at each time B 4 out of them can be pulled. Without loss of generality, the pulled arms are arm 1, arm 2, arm 3, and arm 4, and their current states are 81, 82, S3 and $4. For pairwise comparisons, and get F ( F TT(er ( F1(0s, ozg), ( Ts3); F (o ag asa) and FndF (o Osy with
can have total 6 comparisons
19

---

Published as a conference paper at ICLR 2025
Fm m (o em Sen)) being defined
( F (m Ton) == F((m 1)|8| Jem: (n - 1)|5| + σs.)) = exp(rm (5m)) + exp(rn(sx))
However, Lemma 2 indicates we only need to do B 1-1 3 comparisons and infer the rest of them. For example, we randomly select the comparison between arm and arm arm and arm 3, arm I and arm 4. Hence, we have ; a22): F9 aa)) and (o Tsa). Next, we can infer (o mn)) F3 O..) and (2 Ts.) as follows
(1 F7(81. 82) F1) 83)
3 (52, 93)
(1 (31 82)
F1 ($1 83)
(31, (3) Fi(1,
(1 Ff(s) ($1, 83) (811,
if (s,,
=
(1 (31 83) ) [1 81) F1 81 (11,
(1 (1- (f F
F2 "12, (52,84) 84)
(1 (9 82) [1 (1 (81, 84) (81,
D PROOFS OF LEMMAS IN SECTION 3
In this section, we provide the missing proofs of the lemmas in Section
D.1 PROOF OF PROPOSITION
According to the Bradley-Terry model in 2 we have the preference of arbitrary arm n with arbitrary state s, over the reference arm with reference state s.
(s)(r.(s))
(o.: exp(rx(s)) + exp(rr,ss))
(18)
With standard manipulation, we have
exp(r. - F (o,, exp(rn(s)).
(19)
F; Oe))
Taking logarithms to both sides further leads to
F Fo, oz.) (s) = (s. + In
(20)
(o.)
with the fact that F" (... =1 - This completes the proof.
D.2 PROOF OF PROPOSITION
Recall that the underlying reward for each arm and state rx (s) belongs to the range of [0. 1]. we can easily find that any preference value F lies in the range of lit= - under the Bradely-Terry model in 22. Defining an auxiliary function ((x) = In I-x and taking the derivative of Q(x) with respect to ,. and thus we have
dQ(x) d dx
In
(21)
dx
x01 x)
Notice that dQ(x) > O for x [11e ] and hence Q(x) is monotonically increasing with æ in this domain. Substituting the endpoints into Q(x), we can easily find that Q(x) E [-1, Since F o.,) is in the range of 1 lt.l. we have (s) being monotonically increasing function and bounded in [-1, This completes the proof.
20

---

Published as a conference paper at ICLR 2025
D.3 PROOF OF LEMMA
Define the following event that there exists at least one state-action pair (8, a) of any arm n such that the true transition kernel pk: s, a, lies outside of the confidence ball P (s. a) defined in ( i...
c
(ss(ss > (s.
(22)
The probability that the failure event 1 (E: occur is bounded as follows. We first introduce the Chernoff- Chernoff-Hoeffding Hoeffding inequality (Hoeffding. 1994) in the following lemma.
Lemma 7 (Hoeffding inequality (Hoefiding) 1994). ). Let X2.... be independent random vari-
ables with b S [X,| I for all Define Sn X1 .... Xn, Then for all
6²
Pr (S - -E[sm] > >) & exp
2n(cc b)2
Provided the confidence interval (s, V
In
|| 1)H
we have the following
27 (s,a)
inequality according to Lemma 7 4k 2 2,
2e
P(IPa(s'|s,a)) (s'(s,s, a)]
8th (s. a)) S
(23)
|S||A|NN( 1)H
Using union bound on all states and actions, we have
PP (8)
((IPn(8'ls,, (s))),)) - (5'1os (s,
n=
(s.a)
2c
2c.
(k 1)H
Since the event that P. E Pk is the complementary event of gk p,n. we have that
P(I(PLEPH) P(1 (8), - 2c.
(24)
This completes the proof.
D.4 PROOF OF LEMMA
According to Bradley-Terry model in (2) we have
exp(r;)
exp(r,)
F(j.1)- exp(r,) + exp(ra))
F(.j2) exp(r;) + exp(rrs)
(25)
Hence, we have
exp(rin F(11122) exp(r;,) + exp(ria)
exp(r,)
F(idi)
exp(r:)( 1-F().1)
+ exp(r:) FG.12)
1-FUJ2)
F(J1)
1-F(1-))
F(.hh
1-FUJ1) + I-FU3)
FOJI
F(-22
(1 F(.AA))(G1))
(26)
(1 F(. + (1
F(.A))
where the second inequality is due to 25 That being said, we can infer the exact value of F F(1,jj2) if we have the exact value of F(j.j) and F(j, f2) for arbitrary j.
21

---

Published as a conference paper at ICLR 2025
Now assume that we have the empirical estimated values of F and F(j. satisfying (j.
F(j.ii) S d1 and (2) F(i.j2) S 82 with probability least 2e, and we have the following estimation
(1 FFF().)))F((.))
F (j1.52)
(27)
(1 - (1-F(...)) + F(i.j2) F(.
Our goal is to find the error bound of [F (21, F(i, 12) given òi and 82, which can be expressed
as
(1 -F....))
Fint (1,,22 F(11,22)
(1- F(j.i))) Fe)
(1 F(F...
(28)
- F.-FF..)))..... (1 F(.
To bound (88). we define the auxiliary function f(z, y) Lipschitz continuous in the following lemma.
(1- and show that f(x,y) is 229
Lemma 8. Provide fx,
z+y 2ayy' and have z,
(1 (1=z)y
[ Ite lie) f(x, is Lipschitz continuous,
with valid lipschitz constani L = 1.3.
Proof. To determine whether f(z, y) is Lipschitz continuous over the interval
I+c rff we need
1
analyze the partial derivatives of f(z y) and check they are bounded within this interval. Let us start by calculating the partial derivatives of I with respect to x and y
df v) dx
5²2 -
df v) (x y 2ry)2
I
(29)
(xr tx+ 2ry)
dy
In the given interval of æ and y. the partial derivatives are bounded because both x and y are within closed interval away from O and 1, and thus function fxx y) is Lipschitz continuous, i.c., we have
|f v1) f ve)l S L( x2
1y
V/2 ))
(30)
with I. being the Lipschitz constant. To find the Lipschitz constant J., we need to find the maximum
absolute values of these partial derivatives in the given domain x; E Itte I+c] Therefore, we evaluate these expressions numerically or analytically at the boundary points estimate L. The maximum values of f (z, y)1 and Ify (x. 3) will be determined within these bounds. Finally,
1 I
[
L = max (1, v)l. Ifg (z,v)) v)]} for E
(31)
After numerical evaluation, we can infer that 1.3 and it achieved by dfla.)) which completes the proof.
at 1+c
dg
According to Lemma
we have the following inequality
ina (J1, F(J1,12)
((FO)))))((FFF).. ((FG.)) F(i,2)))
F(.62) F(j.2))
+ (.. -(F(
/(..))). 1(F F(j.22)
22

---

Published as a conference paper at ICLR 2025
+ ((F().)), ((F.)))))-(
h
L( + 62).
(32)
where (a) is due to triangular inequality and (b) comes from the Lipschitz continuity of function f in Lemma 8
D.5 PROOF LEMMA 3
According to Proposition any reward (s) can be equivalently denoted as rs.)) + Qn(s). Then we can rewrite the LP in as
max
Σ
Σ
pa (r(ss
n=
(sa)ESXA
N
S.t.
Σ
( S,
n=1
(5,0)ESXA
()((s,))
Enn's's VnEN,
an( 1I un(s,)) V
(33)
(s,a)E8xA
Hence, the objective can be expressed as
N
N
max
Σ
Σ
(s))
+
Σ Σ (n(s,a)ra($s)
(34)
n=1 (s,0)ESXA
==1 (s,a)SSxA
which equals to
N Σ (s,a)E8xA
max p
(x(
+ Nr.(ss))
(35)
due to the fact that occupancy measure is a probability measure such that E A (n, Therefore, the optimal solution of the LP in (33) is equivalent to
= 1.
max Pr
Σ
an(s,a)(.(9)
(s,a)ESxA
s.t. constraints in 77
This completes the proof.
E PROOF OF THEOREM 1
We first prove that the regret decomposition shown in Lemma and then separately characterize the regret of Term, in Lemma 5 and the regret of Termy in Lemma 6
In this section, we provide detailed proof for the main result in Theorem |
E.1 PROOF OF LEMMA
According to the definition of regret in follows:
3 We can decompose the regret Reg({ 3K T') as
Reg( tm Jk=1 T) op T) )=
23

---

Published as a conference paper at ICLR 2025
J( (T) - J(f vk) (F" V T
Termo 50
+ J(( vk), fF+, vk), T) - J(( vkj, F.
Term
[( vk), F, T) J( vk],
Terma
J( Vke, (F* Vk), T) J [[ wk), F.T)
Termi
([ Vkj, F, T) J([x vk).
(36)
Terms
The key for (36 to hold is to guarantee that Termo S 0, which is shown in the following lemma.
Lemma 9 (Optimism). There exists a set of occupancy measures uaa == {pr (s, a) Vn E N, s E S. a A} under policy x² that optimally solve the LP in (6)-()) In addition, J(xx) for the LP in 6 is no less than J (7 for the original RMAB problem in 77)
Proof. It is straightforward to show that the LP in problem in (1) if the "hard" activation constraint in is relaxed to an averaged one as
6 is equivalent to the original RMAB
lim inf E D. At, S B. To prove Lemme it sufficient to show that the relaxed 7'
problem achieves less average reward than the original problem in (I). The proof is straightforward since the relaxed constraint expands the feasible region of the original problem in (I. Denote the feasible region of the original problem as
N Bt
A
A
VA Σ
A
(37)
n=1
and the feasible region of the relaxed constraint as
T ΣΣ |=|
A
A
Vt
lim inf T-x
ES T
4 < B
(38)
is clear that the relaxed constraint expands the feasible region of the original problem in T ie., A S A' Therefore, the relaxed problem (i.e., the LP in (6)()) achieves an objective value no less than that of the original problem in (I) because the original optimal solution also inside the relaxed feasibility set (Altman] 1999). i.e., A'. Denote the optimal occupancy measures of LP
6 66 as jlz- = [47 a), Vn E N, S, a E A} under a stationary policy n² induced by f a), Yn E A, s E S.a A}. and hence the maximum average reward achieved for the LP in is equal to J(T)). Therefore, follows that (J )) 2 (TTP),, which completes the proof. r
6 66-
Hence, Termo < 0 directly follows Lemma 9
E.2 PROOF OF LEMMA
Since DOPL designs index not directly based on the preference matrix F, but on the preference- reference term Qn(s) defined in Proposition] 2 To characterize the impact the preference- reference term Qn (s) made by the estimation error of F, we first define a general function q(x) := In _ We aim analyze the impact of small perturbation in ær denoted by e, q(x) with the aid of Taylor Series Approximation of q(x). This presented in the following lemma.
Lemma 10. Assume â x + where is small value in (0, 1). Then we have
E
(q( -((x) <
xx1 x)
24

---

Published as a conference paper at ICLR 2025
Proof. We can approximate (()) using first-order Taylor expansion around dq(x) -r).
((0) ((x)
(39)
dx
Following the chain rule, we have the derivative as follows
dq(x) 1-x d I
1
(40)
dx T dr
x I
(1 x)²
x01
x)
Using this derivative, the approximation becomes:
(()) ~ q(x) x(1 - x)
8
(41)
Substitute this into the Taylor expansion:
(e( - g(x)) S
(42)
x(1 2t
This completes the proof.
We need to characterize the performance guarantee of Algorithm 3 which is used for the regret analysis for DOPL. Provided Lemma 7 have the following result w.r.t the estimation of preference matrix F. Hoeffding's Inequality in Lemma 7 states that for independent and bounded random variables S2........ Xn the following holds with probability at least e:
Pr
1
- E[X] 2
n
2exp
-2nd
(43)
(c b)2
Applying this to our Bernoulli trials where and =
(o.,, - (o xxy)) 2 a)
< 2 exp (-20 (si, 8))d))
(44)
We focus on one specific column of the preference matrix F, i.e., F(:, (+ - 1)|5} + J..).
Setting d min Sa muxx (20% (.15).),1) In 41S)LA)N((-1) )
Specifically, when d
max (811) In 118 11S ) we have:
P
(fin* (sn; 8.) (s,, 8.) 2 d) S 2e.
(45)
When d ginl Sn..s we have the inequality in 445 again according to Lemma 2
Next, we begin to bound Termy. For the ease of expression, we define w as the vector containing all w (s, a), vss E S, a E A. and (F) as the vector containing all Qn (s), Vs E S. Then, according to the definition, we can rewrite T d'ermj as
Term1 = J( VkJ, (T* VkJ, T) - J((TM, VK),
K
H
Ww (f*)) Qx.
H
-
+ (F*) (F. (.))))
N (F*)
K N
Σ
(w
Qn (F +
Σ
Ww (f*) (x))), (46)
k=1
k=1
where the second equality is due the definition of # and Lemma
25

---

Term S max Published as a conference paper at ICLR 2025
According to Lemma 10 have
K
N
H
Term1 S max
(w F (:, (+ ()|5) + (a(ss+oos)) - - (;, 1))51 + o..))
F(1,)( - Fii.j)
n=1
K
twh F* (:, ( +..)) - F(:, (+-1)1))
to..)) (1))))))++++)))))
(47)
According to definition of F*t and F*, we have at least probability 1 - 2e based 45 that
K N
Σ
Σ
H
w d:),
(48)
fJ (i,,)(( F(),))
k=
with d R S|x1 being the vector containing all d (s,), Vs,, e S, with (s,)
min ginl
max (8118.).1)
Next, we bound E
E (H wh d in the following lemma.
Lemma 11. The following inequality holds
K
4SI|ANNT VNT.
H wh d S V2[S| In
k=l==1
Proof.
Since di (sp)
min
Snn.s. max(2Ch, (111....
ginl
1 we have
K N
K
[V [maxx(CC (s,, In
4 ||N 1)
18]
ΣV
dk)
H whi
e
k=1n=1
1=1 n=1
1=1 (49)
Hence, the proof goes as follows.
4|S||AANT(K 1)H
H
wh
(V max(2Ch, (st, s.), In
n=1
K
N
4[S|AA 1)H
ΣΣΣ
. w. V max(2(h..ssss.) (8,8)).1) In
8.0
S AINNT
In
ΣΣ> (t, (t) =a1 (3,
(5,0)
AITTT ΣΣΣ (sn(1)) 8, an()) =
In
/ (,,
(8.a)
AINTT
2
Σ
ZT (s,a)
(=,()
AINT
N
Σ E(a.a) 2T. (s,
2
In
Jensen's 's inequality
(S||AA
(d)
AISTTANNT
2v
In
VISIAT due Σ (x, ST
NT
-2
S|AT
26

---

Published as a conference paper at ICLR 2025
S 22v2 In 4|S||A|NT E
NA due to|AA| =
(50)
where (a) follows since w/ is a probability measure. H (s, = (s, (s,a)
=
E (K, h) 8, s,a,(k, h) a), (b) is due to the fact that for any sequence of numbers W1, U2 WT with & Wk. and define Wi= == Ei= Wis we have
Σ wk S2V2/WT.
VWR
1=
(c) follows Jensen's inequality and the fact that E.,o 2n (s,a) = T,, and (d) uses the fact that |A| 2.
This completes the proof.
Bound on Termy. Combining the results in (48) and Lemma we can bound Term; as
Termy S max 2
F(i,))(1 - F), V 2NT[S] 4[8||A|NTT
E.3 PROOF LEMMA
To characterize the regret caused by Term2, we leverage similar techniques from Xiong et al. (2022b). We first introduce the definition of ergodicity coefficient as shown Arapostathis et al. (993); Akbarzadeh & Mahajan (2022), which depicts the transition property of the whole N arms system.
sN]. the corresponding Denote the global state for the whole N-arm system as s E S := [81, $2; actions under the index policy
TT)), and the unknown MDPs as A ( ANl with An = Pn. F,). Hence, we have a transition kernel for the global system as Px(-|s, (s)), Vs E S.V.
The ergodicity coefficient is then defined as follows.
Definition 1 (Ergodicity coefficient). The ergodicity coefficient of a system with transition kernel PA is defined
Dr. = min 8,8'
Σ (s) Pa(2|s', x (s'))),
(51)
ZESV
and D = supA Dpa as the maximum value.
Since the dynamics of the arms independent, the definition of contraction factor implies that sufficient condition is that for every arm, and every pair of state-action pairs, there exists a next state that can be reached from both state-action pairs with positive probability in one step. Let πΛ denote the proposed index policy corresponding to the transition model A and Px be the controlled transition matrix under policy F.. Denote JA as the average reward of policy n and RA does not depend on the initial state and satisfy the average reward Bellman equation (Altman 1999 Puterman 1994
JA + (s) = R(s, TA (s)) + [PAFA)(s), Vs E S.N where (s) is the relative value function.
(52)
To bound T Term,, we first bound the episodic regret J F, H) JTT F, H). Vk.
Lemma 12. With probability at least 2e, the regret for J(#h F,H) [[ F, H) can be expressed as
H Σ
2B
( F,H
FA F (8
+ +1-D D'
where À is the parameter of the optimistic MDP (Pn Vn E..
Proof. The proof goes follows:
J( ((*,,F,1) F) J( F, HJA Σ R(sn: x² (Sh))
H
H
H
R(sh, # (sx)) + - - (F)) Σ
R(s(h), n (sn.)
h=1
h=1
27

---

Published as a conference paper at ICLR 2025
P H
PA - - (s()))
h=1
- [P Fx)(s)) - 11(+++1) + - (sh))
(Al(s)) (sh- 1) 1) +
Fs(s))
H PxF (s(42) + 1-D D
2B
hm1
The equality in (a) directly follows the Bellman equation in (2). (b) is due to the fact that " -h- R(sh, ** (sx)) - R(sn, (sn)), and (c) follows from Lemma in Xiong et al. (2022b).
Then, we bound
- F,7) as follows.
Lemma 13. With probability at least 1 2e, we have the regret bounded conditioned on the good event that the Pk Ph
2V2B
4|S
J( - J( VkJ, F,T) v 1- D DV
log
VNT.
Proof.
From Lemma 12 we can rewrite the summation over J(* F. H) J(T H), 4k as follows:
2BK
1( W.J. - J((#", VKJ.F,T)
1-D
FA (S
(PAM)))((S)) FA4(SN+1)
K
span (Ra) (- and - PA* (115,, (n))
1= 1=1
B
26 (s.a)
2B
T N
log ASIINANT
D
2Z (x,
n=
2B
log
IISTT
ΣΣ Σ [(s,(t)=s'aa)) s', 2Z'
=
1
D
"
(3'.0')
4v2B
4|ST|ANNT
1- D V
log
VN
where (a) follows since E
Σk= Σ' I PA - Fxz (5 = 0, (b) follows standard
linear algebra manipulation
Akbarzadeh & Mahajan 2022). (c) follows the same reason (50).
28

---

Published as a conference paper at ICLR 2025
F EXPERIMENT DETAILS
The code for these experiments is available at this link Some of the experiments presented this paper
M1 Macbook Air and some compute cluster with Dual AMD EPYC 7443 with 48 cores and 256GB RAM.
F.1 APP MARKETING ENVIRONMENT
F.1.1 OVERVIEW
For verbose explanation of the setup refer Appendix B.1 with 4 possible states. Our simulation was carried out with 10 arms in the system and an arm pull budget arms per timestep.
Each user is modeled as a restless arm
F.1.2 SYSTEM DYNAMICS
Transition probabilities:
The transition dynamics are such that without marketing intervention, users tend to decrease in engagement time. Even the most engaged only have 50% chance of staying engaged. On the other hand, if intervened upon, there's a high probability that the user increases in engagement by two levels.
Without intervention:
0.77
0.1
0.1
0.17
0.5
0.3
0.1
0.1
P int
0.2
0.4
0.3
0.1
0.1
0.2
0.2
0.5
With intervention:
0.1
0.1
0.7
0.1
0.1
0.1
0.1
0.7
Pin
0.1
0.1
0.1
0.7
0.05
0.05
0.05
0.85
Rewards:
The latent reward is structured as follows. Higher the engagement level higher the reward.
0.33
R
0.66
F.1.3 HYPERPARAMETERS
Below detail the hyperparameters used during the training.
Hyperparameter
Value
K (Number of Epochs)
4000
H (Horizon)
100
6 (Epsilon)
10-5
Table Hyperparameters used App Marketing Environment Training.
F.2 CPAP ENVIRONMENT
F.2.1 OVERVIEW
For detailed description of the environment refer Appendix B.2 The environment models each patient undergoing sleep apnca treatment as restless arm. The patient can in three possible states based his level of adherence the treatment.
29

---

Published as a conference paper at ICLR 2025
Our simulations consist of 20 patients (arms) only of whom can be intervened with by the doctor at any given time (arm budget).
F.2.2 SYSTEM DYNAMICS
Transition probabilities:
Patients be classified into two clusters based on their transition behaviours, (i) General pattents and (ii)High-risk patients
General Patients (Arm type 1) These patients are very responsive intervention and also adhere to their treatment fairly well even without intervention seen in the transition probabilities below.
Without intervention:
T0.1385
0.1
0.7615
Poo_int
0.1
0.1
0.11257
0.1245
0.7498
With intervention:
00.1
0.1
0.87
P
0.1
0.1
0.8
00.
0.1
0.8
High-Risk Patients (Arm type 2) adhere to their treatments.
These patients need constant intervention in order for them to
Without intervention:
T0.7427
0.0741
0.1832
P Poo_int
0.3399
0.1634
0.4967
0.2323
0,2020
0.6657
With intervention:
T0.1427
0.3741
0.48327
Pit =
0.1399
0.1
0.7601
00.1323
0.1
0.7677
Rewards:
The latent reward is as follows, with higher reward for more adherence.
0.5
1
F.2.3 HYPERPARAMETERS
Below we detail the hyperparameters used during the training.
Hyperparameter
Value
K (Number of Epochs)
300
(Horizon)
1000
(Epsilon)
1 1 10
Table 2: Hyperparameters used in Constructed Environment Training.
F.2.4 EVOLUTION OF ESTIMATION ERRORS THROUGHOUT TRAINING
We monitor and visualize several key errors during the training process to ensure its integrity and effectiveness.
30

---

Published as a conference paper at ICLR 2025
index error This metric quantifies the disparity between the current index estimated by the (DOPL) algorithm and the optimal index derived from solving the optimization problem (6).
F e_erro: This denotes the discrepancy in preference estimation, measured the root mean squared enror between the estimated preference matrix F* iteration ls and the ground truth preference matrix F.
P_ Peerro: This error metric captures the deviation in transition kernel estimate P from the true kernel Pn.
R errro:: This is the aggregate direct reward estimation error across all states and arms, i.c between (n(s) and (s), where Qn(s) == In I-F,(o,.0s, F. (a......) and (x) == In 1-F2(o.....)
F. (o.. where 8, is the
reference state and the reference arm and F is the estimated preference matrix with the upper confidence term added to it.
12
10
Estimation Error
6-
4-
0
200
400
600
800
1000
1200
1400
1600
Episodes
index_erro
F Ferrro
P error
R error
Figure 4: DOPL Estimation Errors During CPAP Training
F.3 ARMMAN ENVIRONMENT
F.3.1 OVERVIEW
For a detailed description refer to Appendix B.3 There are total of 20 beneficiaries in this simulation each modeled by an MDP. These beneficiaries are of three types. Type A beneficiaries who are responsive the treatment but need little push. Type beneficiaries and Type are less responsive to treatment. ensure that a 1:1:3 ratio is maintained among the beneficiary types. The budget constraint allows intervention with maximum of 10 beneficiaries at given timestep.
moderately responsive
F.3.2 SYSTEM DYNAMICS
The dynamics of the system are such that each beneficiary type is associated with a transition matrix defined by specific probability ranges. For each beneficiary, randomly sample transition probabilities within these ranges according to their type, ensuring that the resulting transition matrix valid-the is, all probabilities non-negative and each row to one.
31

---

Published as a conference paper at ICLR 2025
Type A beneficiaries
Transition Matrices:
Action 0 (No intervention):
T0.5 0.95
0 0.90
0.05
P
0.05
0 0.5
0.45 - 0.95
0.05
0.1 0.6
0.35 - 0.85
Action (Intervention):
0.5 - 0.95
0 - 0.90
0.05
P
0.45 0.95
0.5
0.05
0.05
0.1 - 0.6
0.35 - 0.85]
Type B beneficiaries
Transition Matrices:
Action 0 (No intervention):
T..5 - 0.95
0 - 0.90
0.05
0.05
0.1 0.6
0.35 0.85
0.05
0.1 - 0.6
0.35 - 0.85
Action (Intervention):
0.5 - 0.95
0 - 0.90
0.05
0.15 0.65
0.3 - 0.8
0.05
0.05
0.1 0.6
0.35 0.85
Type C beneficiaries
Transition Matrices:
Action (No intervention):
TO.5 0.95
0 0.90
0.05
0.05
0.1 0.6
0.35 0.85
0.05
0.1 0.6
0.35 0.85
Action (Intervention):
0.5 0.95
0 0.90
0.05
P
0.05 - 0.50
0.45 - 0.90
0.05
0.05
0.1 0.6
0.35 0.85
Rewards:
1
=
0.5
0
F.3.3 HYPERPARAMETERS
Below detail the hyperparameters used during the training.
Hyperparameter
Value
K (Number of Epochs)
20000
(Horizon)
5
(Epsilon)
1 1
Table 3: Hyperparameters used in ARMMAN Environment Training.
32


Reviews:
[{"review_id": "XaP04lyllF", "reviewer": "Reviewer_j6r7", "summary": "This work studies a new problem set-up, PREF-RMAB.\nFor me, the problem set-up is very incremental. It is quite similar to duelling bandits. The proposed set-up is more like duelling bandits with state transitions. \n\nThe writing needs to be improved. \n\nThe writing for the intro is too wordy. I wish to see more literature work discussions.\n\nI suggest putting the main theorem (Theorem 1) earlier. I can only see the theoretical result at Page 8. So, the structures for sections 4 and 5 are suggested to re-arrange. \n\nA minor thing: usually, RL or bandit theory works use $\\delta$ to be the failure probability. The greek letter $\\epsilon$ is for something else, like the error rate.\n\nI went through the proofs and some steps are novel, not that typical in bandit/RL literature. But I did not check the correctness of the proofs.", "questions": "see the first box", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "see the first box", "weaknesses": "see the first box", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oW3ddzO57d", "reviewer": "Reviewer_xkaa", "summary": "The paper studies the Restless Multi-Armed Bandits with preference feedback named PREF-RMAB. The authors propose the Direct Online Preference Learning (DOPL) algorithm achieving an $\\tilde{O}(\\sqrt{T \\ln T})$ regret, which is the first to give the theoretical regret upper bound for PREF-RMAB. Moreover, the paper presents numerical experiments which further validate the efficacy of DOPL against various baselines.", "questions": "1.\tEstimating the whole preference matrix $F$ in DOPL algorithm requires large computational cost. Moreover, it would be beneficial to involve a thorough discussion on computational complexity of DOPL.\n2.\tIn experiments, the existing algorithms like MLE_WIBQL, MLE_LP fail to achieve sublinear regret. A detailed discussion on why these algorithms underperform in achieving sublinear regret would provide valuable insights.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1.\tThe paper successfully integrates preference feedback within the RMAB framework, a novel approach that shifts away from traditional scalar reward dependency. Moreover, the presented algorithm DOPL achieves $\\tilde{O}(\\sqrt{T \\ln T})$ regret with theoretical analysis.\n2.\tThe relaxed LP-based direct index policy of DOPL is also given to tackle the limitations of computational intractability.\n3.\tThe writing is clean and easy to follow.", "weaknesses": "1.\tEstimating the whole preference matrix $F$ in DOPL algorithm requires large computational cost. Moreover, it would be beneficial to involve a thorough discussion on computational complexity of DOPL.\n2.\tIn experiments, the existing algorithms like MLE_WIBQL, MLE_LP fail to achieve sublinear regret. A detailed discussion on why these algorithms underperform in achieving sublinear regret would provide valuable insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Jq628u7vby", "reviewer": "Reviewer_FhNw", "summary": "This paper proposes the PREF-RMAB model, which observes only the preference between two arms rather than the exact reward of each arm in the restless multi-armed bandit problem. By expressing the reward function of any arm n  in any state as the sum of a reference reward and a function related to the preference probability between arm n in state s and a reference arm in a reference state, the authors develop a direct index policy based on preference data to choose which arms to activate in the online manner. They establish an O (√(NT|S|ln⁡〖(|S||A|NT)〗 )) regret bound for the proposed algorithm.", "questions": "•\t1. In the 11th step of Algorithm 3 in Section C.3, when inferring \\(\\hat{\\mathbf{F}}_n^{*,k+1,\\text{inf}}(\\sigma_{s_n}, \\sigma_{s_*})\\), only one intermediate column \\( j \\) in \\(\\mathbf{F}\\) is selected to compute \\(\\hat{\\mathbf{F}}_n^{*,k+1,\\text{inf}}(\\sigma_{s_n}, \\sigma_{s_*})\\) based on \\(\\hat{\\mathbf{F}}_n^{*,k}(\\sigma_{s_n}, j)\\) and \\(\\hat{\\mathbf{F}}_n^{*,k}(j, ((*-1)|S|+\\sigma_{s_*}))\\). However, after selecting \\( B \\) arms at each step, the duels are conducted randomly, resulting in many comparison data points beyond \\( j \\) that are not used in the inference process. Could this lead to substantial unutilized information? Could more comparison data, beyond just \\( j \\), be leveraged to infer the preference between \\( s_n \\) and \\( s_* \\)? Alternatively, rather than performing duels randomly, might strategically choosing duel pairs improve performance?\n\n•\t2. In Eq. (3), the authors define \\(\\pi^{opt}\\) as the solution of (1) with scalar rewards, but the footnote states that the regret is with respect to preference feedback, which seems contradictory. This part is unclear to me.\n\n•\t3. In Eq. (46), the suboptimality is accumulated over \\( K \\) episodes. However, since \\( \\omega^k_n \\) is a probability measure and \\( Q_n(s) \\) represents the relative reward of arm \\( n \\) in state \\( s \\), which involves the reward incurred at a specific step \\( h \\) within episode \\( k \\), why doesn’t \\( h \\) appear in this decomposition?\n\n•\t4. In Lemma 6, the authors use Lemma 11 to argue that term0 is negative. However, I find this reasoning unclear, as \\({\\pi^*}\\) does not appear to align with \\(\\tilde{\\pi}\\) as defined in Lemma 6. Specifically, \\(\\mu_{\\pi^*}\\) represents the optimal solution of Eq. (6)-(9), while \\(\\tilde{\\pi}\\) is the index policy developed from \\(\\mu_{\\pi^*}\\) to satisfy the hard constraint. Therefore, I am uncertain that Lemma 11 can indeed be used to prove Lemma 6, and concluding that term0 is negative is not straightforward.\n\n•\t5. In the proof procedure following Eq. (49), from the fourth to the fifth line, the inequality \\(\\sum_{k=1}^K\\sqrt{\\frac{1}{Z^k_n(s,a)}} \\leq \\sqrt{Z^K_n(s,a)}\\) appears incorrect. For instance, if the algorithm visits arm \\( a \\) at state \\( s \\) once at the beginning and never revisits this state, it would hold that \\( Z^1_n(s,a) = \\dots = Z^K_n(s,a) = 1 \\), yielding \\(\\sum_{k=1}^K\\sqrt{\\frac{1}{Z^k_n(s,a)}} = K\\), which is indeed greater than \\( \\sqrt{Z^K_n(s,a)} = 1\\). If I have misunderstood this part, please clarify.\n\n•\t6. In the sentence between lines 1398 and 1399, I think the statement \\(\\sum_{n=1}^N\\sum_{(s,a)}Z^T_n(s,a) \\leq NT\\) should instead be \\(\\sum_{n=1}^N\\sum_{(s,a)}Z^T_n(s,a) = T\\), as the total visits across all arms and states should sum to \\(T\\). In fact, only under this revised statement can the inequality (c) above this sentence be satisfied, otherwise it should be \\(\\sum_{n=1}^N\\sqrt{\\sum_{(s,a)}Z_n^K(s,a)}\\leq N\\sqrt{T}\\). This confusion also appears in the sentence from 1503 to 1505. If I have misunderstood this part, please clarify.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Although RLHF has recently gained significant attention due to its applications in large language models and robotics, this work is the first to consider a preference-based reward model in the restless bandit problem, opening the door for RLHF to be applied much more broadly.\n\n2. By establishing a connection between pairwise preferences and reward values, the authors transform the reward value of each arm and state into a measure based on the preference probability between this state and a reference arm and state, which is intriguing. Additionally, the algorithm can infer the preference between the element j in the preference matrix \\(\\mathbf{F}\\) and the reference elements \\(s_*\\) without directly comparing them, but rather through an intermediate comparator. This clever design reduces the complexity to that of directly observing the reward.", "weaknesses": "•\t1. A question remains as to whether a preference-based model can outperform direct reward estimation, and whether we really need the preference-base model in RMAB problem. In the first two examples presented in the paper, APP MARKETING and CPAP TREATMENT, while reward data is challenging to estimate accurately and may contain substantial noise, it can still be estimated in some form. Conversely, since preference data inherently provides less information, it is unclear whether incorporating preference data can improve performance over direct reward estimation. Most papers on RLHF use preference feedback to shape the reward for different trajectories in robotics or large language models (LLMs), where trajectory rewards are inherently complex and require function approximation methods to estimate the reward function. However, the RMAB model studied in this paper is a tabular MDP, where rewards can be estimated through multiple sampling.\n\n•\t2. In Algorithm 3 of Section C.3, at each step \\( h \\), the algorithm performs \\( (B-1) \\) random duels to obtain the preference data. Then, when constructing the preference between \\(s_n\\) and the reference \\(s_*\\), only the preference between \\(s_n\\) and \\( j \\) and \\(s_*\\) is used. It appears that \\( s_n \\) could be compared with many other columns \\( i \\) in the \\( F \\) matrix, but the algorithm does not leverage this data. Consequently, Algorithm 3 makes inefficient use of the available information.\n\n•\t3. The MDP considered in the paper is essentially a tabular MDP, and the regret scales with the square root of \\( |S| \\) (the size of the state space), which may be inefficient for large state spaces.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XMJPkvPMTf", "reviewer": "Reviewer_mNbh", "summary": "This paper studies the restless multi-armed bandit (RMAB) problem with preference feedback (PREF-RMAB) rather than direct reward estimation, motivated by real-world applications like app marketing and CPAP treatment. To address the problem that some arms in some states may not be visited frequently, the authors propose a new method to infer the empirical average of arm preference via the other arms’ empirical preference estimations. Additionally, the authors transform the original reward-based optimization problem into another one in terms of preference feedback directly. Using this transformation, the authors develop a low-complexity index policy for decision making. They also provide theoretical analysis of the regret bound, establishing a regret bound of $\\tilde{\\mathcal{O}}(\\sqrt{T\\ln T})$. Finally, the authors conduct experiments to verify the performance of their proposed DOPL algorithm.", "questions": "1.\tThe important results Lemmas 4 and 5 are based on Lemma 1. However, it is unclear why there is only a single reference arm * and a single reference state in Lemma 1. In the RMAB setting, DM selects B arms at each time slot, so the use of a single reference arm seems inconsistent.\n2.\tIn Eq. (4), if $\\epsilon=o(1)$, the confidence width becomes arbitrarily large. While if $\\epsilon=\\Theta(1)$, the probability becomes very small. How do the authors balance this trade-off? A more detailed discussion of the setting for $\\epsilon$ would be helpful.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe authors present novel approaches to address the PREF-RMAB problem. The results in Lemmas 4 and 5 are particularly interesting and have the potential to inform future algorithmic design.\n2.\tThe propose DOPL algorithm works well on the PREF-RMAB problem.\n3.\tI understand that analyzing the regret bound of the RMAB problem with preference feedback is challenging, so the inclusion of this theoretical bound is commendable.", "weaknesses": "1.\tAlthough the authors make a strong effort to illustrate potential real-world applications of the PREF-RMAB problem, the justification remains unconvincing. For instance, in the app marketing scenario, users’ state transitions do not satisfy the memoryless Markov chain property, as a user currently in state $s_4$  cannot directly transition to $s_1$, and time tracking is ambiguous. Similar concerns apply to the other examples.\n2.\tThe writing can be further improved. For example, \n\n    (a) Adding more detail on the composition of the preference matrix $\\mathbf{F}$ would improve clarity.\n\n    (b) Eq. (2) needs to be improved, as the notation is confusing. \n\n    (c) The objective function (6) is not easy to follow. Please define $\\mu^{\\pi}$ and $\\mu_n$ first. I misunderstood it as a myopic problem until I saw the definition of mu^pi. \n\n    (d) I think Lemmas 4 and 5 are more important than Lemmas 1 and 2. The authors can change them into propositions. \n\n    (e) Lemma 2 can be improved by defining $Q_n(s)$ first and then present the result in Lemma 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)