DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback

Thank you very much for your review and constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper.

Weakness #1: ...Although the authors make a strong effort to illustrate potential real-world applications of the PREF-RMAB problem, the justification remains unconvincing...

Response: Thank you for your thoughtful comment. We appreciate the opportunity to clarify our intentions and the broader applicability of our Pref-RMAB framework.

Our proposed Pref-RMAB framework is designed to provide a general solution for any RMAB setting where only preference feedback is available, rather than scalar rewards. This distinguishes our work from conventional RMAB formulations that rely on well-defined reward signals (Whittle, 1988; Larrañaga et al.,2014; Bagheri & Scaglione, 2015; Verloop, 2016; Zhang & Frazier, 2021). By directly learning and making decisions based on pairwise preference data, our approach broadens the applicability of RMAB models to contexts where scalar reward estimation may be unavailable, or unreliable.

The examples provided in the paper, such as app marketing and healthcare scenarios, serve to illustrate the potential applications and significance of our proposed setting where in practice, the preference feedback is more naturally rather than scalar rewards. Our primary goal is to demonstrate the applicability and versatility of Pref-RMAB in handling preference-based decision-making in such real-world applications. We acknowledge that in some real-world scenarios, including app marketing, user state transitions may appear to violate the memoryless Markov chain property due to complex dependencies and history effects. However, the Markovian assumption in our Pref-RMAB model serves as an abstraction that simplifies the modeling process while retaining key sequential decision-making dynamics. More importantly, this assumption in practice can be reasonably approximated by defining states in such a way that captures sufficient historical context (e.g., aggregating past behaviors) to make state transitions approximately Markovian. For example, if a user in state $s_4$ cannot transition directly to $s_1$, the state space can be designed to capture intermediate states, transitions, or aggregate behaviors that reflect more realistic movement patterns while preserving Markovian dynamics for computational traceability.

In practice, certain real-world applications may require additional modeling assumptions or extensions to approximate Markovian dynamics effectively. For instance, refining the state space or incorporating historical data may better capture complex transitions. While such adaptations can enhance the fidelity of specific applications, addressing these complexities falls outside the primary scope of this paper. Our focus is on establishing and analyzing the theoretical foundation and performance of the Pref-RMAB framework under the core assumption of Markovian dynamics for tractability.

Weakness #2(a): Adding more detail on the composition of the preference matrix would improve clarity.

Response: We agree with the reviewer and the definition the preference matrix is important for the readers to understand preference learning in Pref-RMAB. Due to space constraints and to help readers better understand this concept, we indeed provided a detailed definition of the preference matrix along with a toy example in Appendix C (lines 942-980).

Weakness #2(b): Eq. (2) needs to be improved, as the notation is confusing.

Response: Equation (2) is the definition of the preference feedback $\alpha(s_m^t,s_n^t)$ between arm $m$ in state $s_m^t$ and arm $n$ in state $s_n^t$. Note that this Bernoulli random variable $\alpha(s_m^t,s_n^t)$ is drawn according to the widely-used Bradley-Terry (BT) model with the detail given in Equation (2). In the popular dueling bandits, each arm is "stateless" and hence the expression corresponding to the BT model is relatively simpler. However, in our Pref-RMAB, each restless arm is stateful which somehow "complicates" the preference matrix as indicated in the preference matrix (see response above), and hence further complicates the definition of Equation (2) correspondingly. Nevertheless, as defined in lines 126-128, "Let $\sigma$ be a permutation on $\mathcal{A},$ and $\sigma_s$ be the position of element $s$ in $\mathcal{A}.$" Thus, the comparison between arm $m$ in state $s_m^t$ and arm $n$ in state $s_n^t$ corresponds to the row $(m-1)|\mathcal{S}|+\sigma_{s_{m}^t}$ and the column $(n-1)|\mathcal{S}|+\sigma_{s_{n}^t}$ in the preference matrix $\mathbf{F}.$ This leads to the first equality in Equation (2), and the second equality is directly from the definition of the BT model. We hope this clarifies the confusion, and if you have other concerns, we are happy to engage further.

Weakness #2(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$.

Response: Thank you for this suggestion. We have modified the paper to define $\mu_n$ and then $\mu^\pi$ first. We highlight the changes in blue.

Weakness #2(d): I think Lemmas 4 and 5 are more important than Lemmas 1 and 2. The authors can change them into propositions.

Response: Thank you for your suggestions. We have changed them into Proposition 1 and Proposition 2. We highlight the changes in blue.

Weakness #2(e): Lemma 2 can be improved by defining first and then present the result in Lemma 2.

Response: Thank you for your suggestion. We modified the paper by defining the preference-reference term before presenting Lemma 2 (now Proposition 2). We highlight the changes in blue.

Question #1: The important results of 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.

Response: Thank you for your thoughtful comment regarding the use of a single reference arm and state in Lemma 1. However, we are afraid that there is a misunderstanding here regarding the reference arm/state and the design of our DOPL algorithm. We appreciate the opportunity to clarify this design choice and its significance in addressing the core challenges of the Pref-RMAB framework.

A key challenge in the \textsc{Pref-RMAB} setting is that the decision-maker (DM) does not have access to scalar rewards for each arm and state; instead, only pairwise preference feedback is available. This makes direct optimization using conventional RMAB methods difficult, as they typically rely on scalar reward values for decision-making and policy evaluation, as the LP in Eqs. (6)-(9) in Section 3.3. Lemma 1 plays a critical role in bridging this gap by establishing a strong connection between scalar rewards and preference feedback. Specifically, it shows that the scalar reward for any arm $n$ in a state $s$ can be represented in terms of the preference feedback with respect to a fixed reference arm $\star$ and a reference state $s_\star$. As stated in Lemma 2 and Remark 3, we therefore can define the ``preference-reference" $Q_n(s)$ to fully represent the preference of arm $n$ in state $n$ in our Pref-RMAB framework.

You point out that the DM needs to select $B$ arms at each time slot. We formulate this problem in Section 3.3 as defined in Equations (6) - (9) where the feedback of each arm $n$ in state $s$ is the scalar reward $r_n(s)$. One key technical contribution in this paper is Lemma 5, where we showed that we can fully transform the objective (6) into an objective in terms of preference feedback. More importantly, the reference arm and state can be any arm and state, as long as they remain fixed throughout the estimation process. This flexibility does not constrain the DM's ability to select multiple arms at each decision epoch but rather serves as a necessary construct to transform preference feedback into a meaningful scalar reward representation.

Given this fixed reference arm $\star$ and reference state $s_\star$, DOPL only learns one specific column of the preference matrix $\mathbf{F}$, i.e., $\mathbf{F}(: ,(\star-1)|\mathcal{S}|+\sigma_{s_\star})$, corresponding to the preference between the reference state $s_\star$ of reference arm $\star$ with any arm $n\in\mathcal{N}$ in any state $s\in\mathcal{S}$, as discussed in Section 3.2 (lines 272-279). This substantially reduces the computation complexity as well. Although the DM selects $B$ arms at each time slot and the reference arm $\star$ is not selected, we can still infer the values in $\mathbf{F}(: ,(\star-1)|\mathcal{S}|+\sigma_{s_\star})$ according to another novel theoretical result in Lemma 4. In summary, the fixed $\star$ and $s_\star$ serve as a bridge to transform the scalar-reward based optimization problem in Equations (6)-(9) to the preference-feedback-based optimization in Eq. (10).

Thank you very much for your review and constructive comments. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper.

Weakness #1: 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...

Response: Thank you for your comment. We would like to explain why reward estimation performs worse than preference feedback numerically and qualitatively.

In our numerical results, as presented in Figures 1, 2, and 3, we compare the DOPL with three benchmark algorithms MLE_WIBQL, MLE_QWIC and MLE_LP, which rely on maximum likelihood estimation (MLE) to convert preference feedback into scalar reward estimates before applying standard RL algorithms (e.g., Whittle-index-based Q-learning for MLE_WIBQL, MLE_QWIC and linear programming for MLE_LP). As shown in Figures 1, 2, and 3 (left), DOPL significantly outperforms all considered baselines and reaches close to the oracle. In addition, DOPL is much more computationally efficient since it can directly leverage the preference feedback for decision making, while the considered baselines require a reward estimation step via MLE in the presence of preference feedback, which can be computationally expensive. Finally, our DOPL yields a sublinear regret as illustrated in Figures 1, 2, 3 (right), consistent with our theoretical analysis (Theorem 1), while none of these baselines yield a sublinear regret in the presence of preference feedback.

The underlying reason is that these indirect approaches inherently introduce noise and estimation errors during the transformation from preference-based data to scalar rewards. Converting preference feedback into scalar rewards typically assumes that an accurate mapping function exists. However, in complex dynamic environments modeled by the \textsc{Pref-RMAB} framework, such mappings can be non-linear, unknown, or resource-intensive to approximate correctly. As those benchmark algorithms need to design index-based policies (such as Whittle index, and LP-based index), which can be very sensitive to the estimation error. Thus, the cumulative effect of these inaccuracies during each decision epoch leads to suboptimal action selection, resulting in higher regret. In contrast, DOPL circumvents this issue by directly learning from preference feedback, eliminating the need for a reward transformation step. This direct approach allows DOPL to leverage preference data more effectively for decision-making, reducing the impact of noise and achieving sublinear regret.

Furthermore, as we discussed in lines 69-82, "a straightforward method as inspired by RLHF is to learn a scalar reward function to represent the preference feedback of humans, and then apply existing RL algorithms for RMAB with this estimated reward function to the \textsc{Pref-RMAB} problem." However, the downside of directly applying this RLHF method to \textsc{Pref-RMAB} is its complexity and insufficiency. "In view of these issues, there is an innovative line of work that directly learns from preferences without explicit reward modeling, such as the popular direct preference optimization (DPO)". However, most of these RLHF or DPO methods are offline, leading to the issues of overoptimization, while the decision maker in our \textsc{Pref-RMAB} interacts with the environment in an online manner. We kindly refer the reviewer to lines 69-82 for more detailed discussions.

Last but not least, the context of LLMs significantly differs from our RMAB settings. In RMAB, each "restless" arm is a MDP with state transitions and rewards being well-defined (see Section 2.1). In contrast, LLM outputs and the associated feedback are highly context-dependent and subjective. Therefore, despite that both our \textsc{Pref-RMAB} and LLMs consider "preference feedback", the settings and intrinsic nature differ dramatically, and hence are not quite comparable. To our best knowledge, LLMs cannot be formulated as a RMAB problem, and hence our RMAB cannot be viewed as a LLM.

Weakness #2: In 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.

Response: Thank you for your observations. We appreciate the opportunity to elaborate on why these algorithms fail to achieve sublinear regret in our experimental settings, providing valuable insights into their limitations in the presence of preference feedback in practice.

Note that WIBQL (Whittle-index based Q-learning) and LP (linear programming) were designed for the conventional RMAB setting with scalar rewards. Both approaches are guaranteed to converge asymptotically. However, they are not guaranteed with a finite-time performance bound (i.e., a sublinear regret). To make them compatible with the presence of preference feedback, we introduced MLE_WIBQL and MLE_LP on top of them, i.e., MLE_WIBQL and MLE_LP rely on maximum likelihood estimation (MLE) to convert preference feedback into scalar reward estimates before applying the corresponding WIBQL and LP algorithms. This indirect approach inherently introduces noise and estimation errors during the transformation from preference-based data to scalar rewards. The cumulative effect of these inaccuracies during each decision epoch leads to suboptimal action selection, resulting in higher regret. In addition, converting preference feedback into scalar rewards typically assumes that an accurate mapping function exists. However, in complex dynamic environments, e.g., the RMAB with preference feedback as modeled by our proposed \textsc{Pref-RMAB} framework, such mappings can be non-linear, unknown, or resource-intensive to approximate correctly. Different from these existing methods, our DOPL circumvents this issue by directly learning from preference feedback, eliminating the need for a reward transformation step. This direct approach allows DOPL to leverage preference data more effectively for decision-making, reducing the impact of noise and achieving sublinear regret.

Thank you very much for your review and constructive comments, as well as giving the positive rating of our work. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper.

Weakness #1: Estimating 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.

Response: Thank you for your valuable feedback on the computational complexity of the DOPL algorithm, specifically concerning the estimation of the preference matrix $\mathbf{F}$. We would like to emphasize the following aspects and design choices in our paper that address this "complexity" challenge:

Only Need to Learn One Column in $\mathbf{F}$. It is true that a direct estimation of the entire preference matrix $\mathbf{F}$ would indeed require a substantial computational effort. However, a key observation in this paper (Lemmas 1-2) is that the reward for arm $n$ in any state $s$ can be expressed by the reward of a reference arm $\star$ in a reference state $s_\star$. Specifically, as we discussed in Remark 2 and Remark 3, the preference of arm $n$ in state $s$ can be well represented by $Q_n(s):=\ln\frac{\mathbf{F}_n^\star(\sigma_s, \sigma\_{s\_\star})}{1-\mathbf{F}_n^\star(\sigma_s, \sigma\_{s\_\star})},$

which we call the "preference-reference term". Therefore, to estimate the preference of arm $n$ in state $s$ or the value of $Q_n(s)$, DOPL only needs to learn one specific column of the preference matrix $\mathbf{F}$, i.e., $\mathbf{F}(: ,(\star-1)|\mathcal{S}|+\sigma_{s_\star})$ (see discussions in lines 272-279). This corresponds to the preference between the reference state $s_\star$ of reference arm $\star$ with any arm $n\in\mathcal{N}$ in any state $s\in\mathcal{S}$. As we discussed later (Remark 2 and Lemma 5), the design of our DOPL is regardless of the choice of this reference arm and its reference state.

Reduction in Computational Complexity through Preference Inference. In addition, our DOPL introduces a novel preference inference mechanism (Step 3 of Section 3.2) to mitigate the comparison cost. Rather than estimating the preference between all pairs of activated arms in each time slot, DOPL leverages empirical preference estimates from comparisons of a "limited" number of arms and infers the preferences for less frequently observed states using relationships derived from other estimated pairs, as depicted in Lemma 4. Specifically, for any pair $(j_1, j_2)$, the inferred preference $\hat{\mathbf{F}}^{inf}(j_1, j_2)$ is computed using previously established empirical estimates $\hat{\mathbf{F}}(j, j_1)$ and $\hat{\mathbf{F}}(j, j_2)$ from comparisons involving an intermediary reference arm $j$. The inference step significantly reduces the number of comparisons required to maintain an accurate preference estimation. More specifically, we analyze the complexity of DOPL in terms of the number of comparisons and updates required. A naive estimation approach for a preference matrix involving $B$ activated arms at each time slot would necessitate $O(B^2)$ comparisons. In contrast, the preference inference in our DOPL reduces this requirement to $O(B-1)$ comparisons by leveraging transitive relationships, thereby improving computational efficiency while maintaining robust estimation guarantees.

Computational Complexity of DOPL. As discussed in Section 3 (lines 209-213), there are three key components in DOPL: (i) construct confidence set; (ii) online preference learning; and (iii) direct index policy design. The computations mainly come from the second and third components, both of which are linearly in the number of arms and the size of state space. Specifically, the online preference learning (Section 3.2) needs to infer the specific column of preference matrix $\mathbf{F}$ and its computational complexity is linear in the number of arms $N$ , and the dimension of state space $|\mathcal{S}|$ . Similarly, the direct index policy design (Section 3.3) needs to solve an LP, for which the computational complexity grows linearly with the number of arms $N$ , and the dimension of state space $|\mathcal{S}|$. Hence, the computational complexity of DOPL scales well with larger inputs.

Thank you very much for your review and constructive comments. Here we would like to address the reviewer's concerns and hope that can help raise the rating of our paper.

Comment 1: ...compare with dueling bandits...

Our Response: Thank you for your comment, however, we are afraid that we cannot agree with the reviewer on this comment. First of all, we would like to highlight that this paper studies the restless multi-armed bandits (RMAB) problem, which dramatically differs from the widely studied multi-armed bandit (MAB) problem, including the dueling bandits, for online decision making. Each ``restless'' arm in RMAB is modeled as an Markov decision process (MDP) with a state evolving according to a transition function, while arms are stateless in conventional MAB or in dueling bandits. Although RMAB has been widely used to model sequential decision making with instantaneous/hard constraint, it is computationally intractable and PSPACE-hard (Papadimitriou & Tsitsiklis, 1994). In addition, even compared to the standard RL setting where the agent interacts with a single MDP to optimize cumulative reward, RMAB encompasses multiple MDPs, coupled through an instantaneous/hard constraint that limits the number of arms the DM can activate at any time slot.

This coupling, due to the shared constraint, introduces a layer of complexity and interdependence absent in single-MDP RL scenarios. A well-known key technical challenge for RMAB problems is how to develop "low-complexity'' solutions in either offline or online settings for decision makings with the goal to maximize the objective in Eq. (1) while strictly satisfy the instantaneous/hard constraint in each time slot. See detailed discussions on the challenges below. Hence, our \textsc{Pref-RMAB} is NOT ``simply'' an incremental setting of the dueling bandit setting with state transitions.

Secondly, it is known that in a dueling bandit setting, the agent/decision maker selects a pair of arms $(k_{+1,t}, k_{-1,t})$ from the set $[N]$ at each time slot $t$ and a preference feedback $\alpha_t \sim \text{Ber}(P_t(k_{+1,t}, k_{-1,t}))$ is revealed, with $P_t(k_{+1,t}, k_{-1,t})$ being the probability of arm $k_{+1,t}$ being preferred over arm $k_{-1,t}$. The goal is to find the best arm $k^*$ to minimize the total loss measured w.r.t. the single fixed arm $k^* \in [N]$ in hindsight, i.e.,

$

R_T(k^) := \sum_{t=1}^{T} \frac{1}{2} \left( P_t(k^, k_{+1,t}) + P_t(k^*, k_{-1,t}) - 1 \right).

$

In such a dueling bandit setting, it is known that a single best arm can be found by preference feedback only with multiple rounds. In contrast, in our proposed \textsc{Pref-RMAB} setting, the goal is to solve the following problem (derived from Lemma 5):

with $\star$ being a reference arm, $s_\star$ being a reference state for the reference arm, and $Q_n(s)$ being the ``preference-reference" term defined in Lemma 2.The goal in \textsc{Pref-RMAB} is not to find a best arm at every time step, but instead to leverage preference feedback to design a sequential decision-making policy for the coupled MDP problem. To achieve this goal, there are many unique challenges in our proposed \textsc{Pref-RMAB} setting as follows: