acceptodds
Under review as a conference paper at ICLR 2027

From Dueling Bandits to Episodic MDPs: Learning with Adversarial Preference Feedback

Abstract

In dueling bandits, the learner compares two arms in each round and observes only which one is preferred. This paper asks what changes when the compared pair also affects the next state, as in a recommendation interface where the pair shown to a user affects the user's next context. We formulate this problem as a state-wise preference-based MDP, an episodic tabular MDP in which the learner selects a pair of arms at each visited state, observes only a noisy comparison between them, and moves to a next state that may depend on the pair. The preferences may change adversarially across episodes, and the loss of a pair is defined through Borda scores. We show that the minimax regret of this problem under known transitions is , where , , , and are the numbers of steps per episode, states, arms, and episodes, and that this rate is achieved by an algorithm based on online linear optimization over the set of occupancy measures. If the pair did not affect the next state, each state would be a separate dueling bandit, and the term of the minimax regret would be smaller by a factor of , demonstrating the cost of having action-dependent state transitions. We also give a policy optimization algorithm with closed-form updates, whose regret is up to lower-order terms, and we extend both algorithms to unknown transitions.

Primary area:
learning theory
Keywords:
dueling bandits, episodic MDPs, adversarial preferences, Borda scores

Reviews

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

The authors study episodic tabular MDPs with adversarial state-wise preference feedback, where the learner selects a pair of arms at each visited state and observes a noisy comparison. The regret is measured using Borda-induced losses against the best fixed policy in hindsight. For known transitions, they obtain an expected regret bound of O~((H3SK)1/3T2/3)\widetilde{O}((H^3SK)^{1/3}T^{2/3}), where HH, SS, KK, and TT denote the episode length, the number of states in the layered MDP, the number of arms, and the number of episodes, respectively. They also provide a policy optimization bound of O~((H4SK3)1/3T2/3)\widetilde{O}((H^4 SK^3)^{1/3} T^{2/3}), and extend both guarantees to unknown transitions. The authors finally establish a lower bound of Ω((H3SK)1/3T2/3)\Omega((H^3SK)^{1/3}T^{2/3}).

Critical strengths

As first strength, I find the theoretical results quite comprehensive. The authors provide upper bounds for both known and unknown transitions, together with a lower bound that matches the occupancy-based algorithm guarantee. They also study both occupancy-based algorithm and policy optimisation.

I also find the paper reasonably well written and well organised. The authors did their best in providing a good summary of the many results provided (even if some key ides behind the algorithm could be better explained).

Critical weaknesses

My main concern is the about the technical novelty of the paper. The algorithms and analyses appear to mainly combine well known methods for adversarial MDPs, such as OMD over occupancy measures and policy optimization with bonuses, with standard ideas for estimating Borda scores in dueling bandits.It is not sufficiently clear to me how the ideas of the paper go beyond combining the existing approaches. I think the authors should provide a more direct comparison with these methods, explaining what a straightforward combination would achieve, where it would fall short, and which additional ideas are essential for obtaining their guarantees.

Given the previous concern, for now, I am not convinced that the technical contribution is substantial enough to meet the acceptance bar.

Questions for authors

See Weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 7rvg

Thank you for taking the time to read our paper and provide a helpful review. Below are our responses to the review.

Comparison with a direct combination of existing methods (W1)

The algorithms and analyses appear to mainly combine well known methods for adversarial MDPs [...] I think the authors should provide a more direct comparison with these methods, explaining what a straightforward combination would achieve, where it would fall short, and which additional ideas are essential for obtaining their guarantees.

The upper bound of global optimization is, as the review says, essentially a combination of existing methods. Still, the analysis requires some care, and this upper bound, which matches the lower bound up to logarithmic factors, is needed to characterize the minimax regret.

More importantly, as explained in Sections 5 and 6 of the submitted version (at the lines cited below, numbered as in the revised version), our results on the lower bound and policy optimization cannot be obtained by a straightforward combination of existing methods. For the lower bound, such a combination gives a rate that is smaller by a factor of H1/3H^{1/3} (Lines 454–472). For policy optimization, the estimate of the Q-function used with loss feedback has no direct counterpart under preference feedback, and the standard analysis does not apply directly (Lines 368–380 and 401–411).

Below, we emphasize the main differences from what a straightforward combination gives, in particular for the lower bound and for policy optimization.

  1. Lower bound (Theorem 3). A straightforward combination, which embeds the lower bound for dueling bandits at each state, cannot give more than Θ~(min⁡{HT,(H2SK)1/3T2/3})\widetilde\Theta(\min\lbrace HT,(H^2SK)^{1/3}T^{2/3}\rbrace), the minimax regret when the transitions do not depend on the displayed pair (Appendix F). To obtain the additional factor of H1/3H^{1/3} in the lower bound, we need to construct a new instance, in which every comparison that helps to identify the Borda winner moves the learner to states with larger losses for the rest of the episode (Figure 1). With this lower bound, the paper shows that the minimax regret under known transitions is Θ~(min⁡{HT,(H3SK)1/3T2/3})\widetilde\Theta(\min\lbrace HT,(H^3SK)^{1/3}T^{2/3}\rbrace), which is its main result.
  2. Policy optimization (Theorem 2). The estimate of the Q-function used with loss feedback sums the losses observed along the trajectory (Luo et al., 2021), whereas with preference feedback the losses are not observed. The comparison of the executed pair carries no information on the Borda loss of this pair, so this estimate has no direct counterpart. The additional idea is the estimator (10). It combines the losses of all pairs at a visited state, estimated from a single comparison of a uniformly random pair there, with the losses at later steps, estimated from the executed trajectory. Lemma 16 states the argument of Luo et al. (2021) in a form that applies to any nonnegative estimate, since the estimate (10) has a different mean and a second moment that depends on KK and γ\gamma.
  3. Global optimization (Theorem 1) and unknown transitions (Theorems 8 and 17). Theorem 1 combines FTRL over occupancy measures with the estimation of Borda scores from comparisons of uniformly random pairs. The one point that needs care is stated in Lines 254–261. The estimator of Saha et al. (2021) draws the two arms independently, which would in general change the next-state distribution in MDPs, since the next state depends on the displayed pair. To avoid this, we build the random comparisons into the decision set of FTRL instead. The extensions to unknown transitions add the confidence sets of Jin et al. (2020a) to the two algorithms (Sections 4.2 and 5.2).

We have added the comparison for policy optimization to the introduction, with a reference to Section 5.1 (Lines 89–94).

Reviewer_e6VTOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies episodic tabular MDPs in which the learner selects an ordered pair of arms at each visited state, observes a binary preference, and moves according to a fixed transition kernel that may depend on the pair. Preferences can vary across episodes under an oblivious adversary. Losses are defined by the average Borda loss of the two arms, and regret is measured against the best fixed Markov policy in hindsight. For known transitions, an occupancy-measure FTRL algorithm achieves expected regret O~(min⁡{HT,H(SK)1/3T2/3})\widetilde O(\min\{HT,H(SK)^{1/3}T^{2/3}\}), where SS counts layered states. A matching lower bound holds for H≥3H\geq3, K≥5K\geq5, and S≥2HS\geq2H. The paper also develops a policy optimization algorithm with closed-form updates and a worse leading dependence on HH and KK, and extends both methods to unknown transitions. Small synthetic experiments with known transitions illustrate regret scaling and runtime differences.

Critical strengths
  • A sharp characterization with a consequential lower bound. Theorems 1 and 3 match up to logarithms. The hard instance makes informative comparisons. Appendix F then identifies the smaller rate with pair-independent transitions: it explains a structural source of difficulty in sequential preference learning, rather than merely providing another regret upper bound. The fact that stationary preferences suffice for the lower bound further clarifies the source of hardness.

  • A coherent algorithmic treatment of preference feedback. Incorporating uniform comparisons directly into the feasible occupancy set ensures that the executed occupancy equals the FTRL iterate. This allows the inverse state-visit probability in the estimator's variance to cancel against the occupancy weight, yielding the SK/ρSK/\rho term in Lemma 5. The policy method contributes a carefully conditioned preference-based QQ estimator, and the unknown-transition extensions broaden the theoretical treatment. These ingredients make the upper bound convincing and useful beyond a purely existential result.

Critical weaknesses

The application relevance of the model is insufficiently established. Pair-average Borda loss is a specific objective, not directly the utility of the clicked item or satisfaction with a displayed set. Uniform opponent weighting depends on the candidate set, and the permitted self-comparisons require interpretation in an interface that displays two items. Moreover, if the next context depends on which item is clicked, changing preference probabilities generally induce changing transition probabilities; the fixed-kernel assumption needs justification in this example.

Questions for authors
  • Clarification of the intended model. In the recommendation example, what mechanism allows comparison probabilities to change while the transition kernel remains fixed, especially if the next state depends on the clicked item? What operational objective motivates pair-average Borda loss and the use of self-comparisons? A concrete example would strengthen the application motivation.

  • Clarification of the computational claim. For the reported experiments, does policy optimization retain an advantage when comparing time to a common regret-per-step target, rather than time for a fixed number of episodes? What solver tolerances and feasibility checks were used for the global FTRL update? This would help distinguish an algorithmic tradeoff from implementation effects.

  • Clarification of the unknown-transition claim. Is optimality intended only asymptotically in TT with H,S,KH,S,K fixed? Can the main result summary explicitly retain the S4S^4 terms and identify a regime in which the extension gives a useful guarantee? I am asking for the scope of the existing result, not a new minimax theorem.

3 comments
AuthorsOpenReview ↗

Response to Reviewer e6VT (1/3)

Thank you very much for taking the time to review our paper and providing valuable feedback. Below are our responses to the review.

Fixed transition kernel in the recommendation example (W1, Q1)

[...] if the next context depends on which item is clicked, changing preference probabilities generally induce changing transition probabilities; the fixed-kernel assumption needs justification in this example. [...] In the recommendation example, what mechanism allows comparison probabilities to change while the transition kernel remains fixed, especially if the next state depends on the clicked item? [...] A concrete example would strengthen the application motivation.

The transition kernel remains fixed while the preference probabilities change when the next context depends on the displayed pair and not on the click. This is the case intended in the example of the paper, where the pair shown affects the next context. If the next context depends on the clicked item, we agree that changing preference probabilities changes the transition probabilities, and our results then apply only when the preference probabilities are fixed.

For a concrete example, consider a video feed in which each screen shows two videos and the user picks one, and let each episode be the session of one user. Let the context be the genres of the two videos shown on the previous screen. A user who has just been shown two action videos is less likely to pick another action video on the next screen, whichever video was picked. The context thus affects the preferences, and it is determined by the displayed pair alone. The transition kernel is therefore the same in every session, whereas the preference probabilities differ between users, and hence across episodes.

When the next context depends on the clicked item, the transition kernel depends on the preference probabilities, and it is fixed when they are the same in every episode. To see this, suppose that the next context is drawn from a distribution Pitem(⋅∣s,i)P^{\mathrm{item}}(\cdot\mid s,i) if item ii is clicked at context ss. Let Pt(s,(i,j))\mathsf P_t(s,(i,j)) denote, as in the paper, the probability that item ii is preferred to item jj at context ss in episode tt. After the pair (i,j)(i,j) is displayed, the next context then has the distribution Pt(s,(i,j))Pitem(⋅∣s,i)+(1−Pt(s,(i,j)))Pitem(⋅∣s,j).\mathsf P_t(s,(i,j))P^{\mathrm{item}}(\cdot\mid s,i)+\bigl(1-\mathsf P_t(s,(i,j))\bigr)P^{\mathrm{item}}(\cdot\mid s,j). Note that Pt\mathsf P_t is a preference probability, whereas PitemP^{\mathrm{item}} is a distribution over next contexts. If Pt\mathsf P_t is the same in every episode, this distribution is a fixed transition kernel that depends only on the displayed pair. It is unknown to the learner, since it involves Pt\mathsf P_t, and the regret bounds for unknown transitions (Theorems 8 and 17) remain valid. Their proofs do not use the independence of the comparison outcome and the next context given the displayed pair, so they apply without change.

If Pt\mathsf P_t changes across episodes, the kernel changes with it, and the setting is outside our model. For general MDPs with bandit feedback whose transitions change adversarially, it is known that sublinear regret is possible only with an exponential dependence on the episode length (see Jin et al., "No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions", NeurIPS 2023, and the references therein). In the present case, the transitions change only through Pt\mathsf P_t, and we do not know whether this structure allows guarantees comparable to ours. The conclusion of the revised version lists this extension as future work (Lines 488–491).

AuthorsOpenReview ↗

Response to Reviewer e6VT (2/3)

Borda loss and self-comparisons (W1, Q1)

Pair-average Borda loss is a specific objective, not directly the utility of the clicked item or satisfaction with a displayed set. Uniform opponent weighting depends on the candidate set [...] What operational objective motivates pair-average Borda loss [...]?

The Borda score of an item is the probability that the user prefers it to an item drawn uniformly from the KK candidates. Minimizing the Borda loss thus means displaying items for which this probability is as large as possible. We agree that this is one specific objective, that it is relative to the candidate set, and that it is not the utility of the clicked item. Preference feedback admits several objectives, such as those based on the Condorcet, Borda, and von Neumann winners, and even in dueling bandits, which correspond to S=H=1S=H=1 of our formulation, they lead to different problems that are studied separately with different algorithms.

We focus on the Borda winner because it exists for arbitrary preferences, including cyclic and changing ones, for which a utility model or a Condorcet winner need not exist, and its minimax regret is known for adversarial dueling bandits (Saha et al., 2021). These make it a natural first objective with which to instantiate state-wise PbMDPs and to study the effect of state transitions. The paper leaves the other objectives for future work, as mentioned in Sections 3 and 7.

[...] the permitted self-comparisons require interpretation in an interface that displays two items. [...] What operational objective motivates [...] the use of self-comparisons?

Self-comparisons are needed since, under the Borda loss, the smallest loss is attained by displaying the best item in both slots. More precisely, when a single item has the largest Borda score, every pair of distinct items has a larger loss, so a learner restricted to pairs of distinct items would in general incur linear regret. The same holds for Saha et al. (2021), whose learner draws the two arms independently and hence also selects pairs (i,i)(i,i). A self-comparison (i,i)(i,i) corresponds to showing item ii alone or in both slots.

Running time at a common level of regret, and solver settings (Q2)

For the reported experiments, does policy optimization retain an advantage when comparing time to a common regret-per-step target, rather than time for a fixed number of episodes?

The advantage of policy optimization is its computational cost per episode, and it does not extend to the running time needed to reach a common level of regret. This advantage is common to all existing work on policy optimization for adversarial MDPs (Shani et al., 2020; Luo et al., 2021; Dann et al., 2023; Li et al., 2026b). In theory, its regret bound is larger than that of global optimization, by the factor H1/3K2/3H^{1/3}K^{2/3} in the leading term (Section 5.2), in exchange for updates that need no convex program. It thus needs more episodes to guarantee the same regret per step in theory, and in the reported experiments, its shorter running time per episode does not compensate for this (Figures 3 and 5). We have slightly revised the introduction to state that the advantage is per episode and comes at the cost of a larger regret (Lines 84–85 and 116–117).

What solver tolerances and feasibility checks were used for the global FTRL update? This would help distinguish an algorithmic tradeoff from implementation effects.

In the reported runs, the global FTRL update was solved with a stopping tolerance of 10−1110^{-11} or smaller, and no solve failed.

In the experiments on the problem size and the running time (Figures 4 and 5), the implementation eliminates the flow constraints of the decision set Ωρ\Omega_\rho using the chain structure of the instances. The convex program then reduces to a small program for each chain, which is solved by SLSQP (SciPy) with analytic gradients and a stopping tolerance of 10−1110^{-11} on the objective value. The program is solved again only for the chains whose loss estimates have changed, starting from the previous solution, and at most 2727 iterations were needed. A solution is accepted only if the solver reports success and the linear constraints are violated by less than 10−910^{-9}, and the largest violation in these runs was 1.33×10−151.33\times10^{-15}. In the experiment varying TT (Figure 3), the program reduces to a one-dimensional problem, which is solved by bisection up to a first-order gap of 10−1310^{-13}. These settings are those of the code in the supplementary material.

AuthorsOpenReview ↗

Response to Reviewer e6VT (3/3)

Scope of the bounds for unknown transitions (Q3)

Clarification of the unknown-transition claim. Is optimality intended only asymptotically in TT with H,S,KH, S, K fixed?

Optimality is claimed only under known transitions, where the bounds of Theorems 1 and 3 match up to a logarithmic factor for every TT. Under unknown transitions, the statement that estimating the transitions adds only lower-order terms refers to the dependence on TT for fixed HH, SS, and KK, which is the usual convention for regret bounds in online learning.

Can the main result summary explicitly retain the S4S^4 terms and identify a regime in which the extension gives a useful guarantee? I am asking for the scope of the existing result, not a new minimax theorem.

The introduction of the revised version now states the bounds for unknown transitions with their S4S^4 terms (Lines 99–100). They are O~((H3SK)1/3T2/3+HSKT+HS4K2)\widetilde O((H^3SK)^{1/3}T^{2/3}+HSK\sqrt T+HS^4K^2) for global optimization and O~((H4SK3)1/3T2/3+H2SKT+H2S4K2)\widetilde O((H^4SK^3)^{1/3}T^{2/3}+H^2SK\sqrt T+H^2S^4K^2) for policy optimization, as the originally submitted version states in Sections 4.2 and 5.2 and in Theorems 8 and 17.

Up to logarithmic factors, the T2/3T^{2/3} term dominates the other two terms when T≥max⁡{(SK)4,S11/2K5/2}T\ge\max\lbrace (SK)^4,S^{11/2}K^{5/2}\rbrace for global optimization and when T≥max⁡{H4S4,HS11/2K3/2}T\ge\max\lbrace H^4S^4,HS^{11/2}K^{3/2}\rbrace for policy optimization. In this regime, each bound reduces to its T2/3T^{2/3} term, which is the same as under known transitions up to logarithmic factors. The bound for global optimization then matches the lower bound of Theorem 3, which also holds for unknown transitions, up to logarithmic factors. For smaller TT, the bounds remain valid, but the additive terms are not negligible.

Additive lower-order terms are common in existing bounds for adversarial MDPs with unknown transitions (Jin et al., 2020a; Luo et al., 2021; Dann et al., 2023; Li et al., 2026b), and they are often not displayed in the abstract or the introduction, since the focus is on the regime of large TT. Our S4S^4 terms are inherited from Dann et al. (2023, Lemma C.4) (and Luo et al. (2021)), as noted after Theorem 8, and are not specific to our paper.

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

This paper studies a well-motivated problem that extends the traditional dueling bandit setting to sequential decision-making. In standard dueling bandits, two arms are compared, and the learner observes which one is preferred. The authors extend this setting by considering what happens when the compared pair also affects future states. To address this, they introduce state-wise preference-based MDPs, where the learner receives noisy pairwise preference feedback at visited states.

The paper makes four principal contributions:

  1. Extends adversarial dueling bandits to sequential decision-making with pair-dependent state transitions.

  2. Develops an occupancy-measure-based learning algorithm that achieves sublinear regret.

  3. Introduces an alternative method with closed-form policy updates, avoiding global convex optimization at the cost of a weaker regret bound.

  4. Establishes that the global optimization algorithm is minimax optimal up to logarithmic factors and quantifies the additional difficulty introduced by pair-dependent transitions.

Critical strengths
  1. The transition from dueling bandits to sequential decision-making is meaningful and well-motivated. Existing adversarial dueling-bandit formulations generally do not account for how comparisons affect future states.

  2. The authors establish both upper and lower regret bounds, showing that their global optimization approach is nearly optimal. This is a significant theoretical contribution, as it characterizes the difficulty of learning from preference feedback in sequential environments.

  3. The paper presents two complementary approaches. The global optimization method provides stronger theoretical guarantees, while the policy optimization method is computationally more efficient. This provides an interesting trade-off between statistical and computational efficiency.

Critical weaknesses
  1. The experimental evaluation does not sufficiently validate the theoretical contributions. The experiments are conducted on synthetic environments constructed using the same setting as the theoretical lower-bound analysis. Moreover, the experiments do not evaluate changing adversarial preferences or unknown transitions, despite these being important parts of the proposed framework. Evaluating the algorithms under more diverse settings would strengthen the empirical claims.

  2. The connection between the proposed formulation and practical sequential preference learning is not entirely clear. The framework assumes that future states depend on the pair of arms presented, rather than on which arm is actually preferred. In many real-world applications, such as recommendation systems, the user's preference or selection directly influences future interactions. It is unclear whether the theoretical guarantees would extend to such settings, limiting the generality of the proposed formulation.

Questions for authors
  1. Could the authors evaluate the proposed algorithms in more diverse environments, particularly with adversarially changing preferences and unknown transitions, to better validate their theoretical contributions?

  2. How would the proposed framework and its theoretical guarantees change if future state transitions depended on the observed preference outcome rather than only on the compared pair?

1 comment
AuthorsOpenReview ↗

Response to Reviewer LT3C

Thank you very much for taking the time to review our paper and providing helpful comments. Below are our responses to the review.

Experiments with changing preferences and unknown transitions (W1, Q1)

The experiments are conducted on synthetic environments constructed using the same setting as the theoretical lower-bound analysis. Moreover, the experiments do not evaluate changing adversarial preferences or unknown transitions, despite these being important parts of the proposed framework. [...] Could the authors evaluate the proposed algorithms in more diverse environments, particularly with adversarially changing preferences and unknown transitions, to better validate their theoretical contributions?

Following this suggestion, we conducted a new experiment with changing preferences, under known and under unknown transitions. The results are reported in Appendix G.5 and Figure 6 of the revised version. For both algorithms and both transition settings, the regret per episode, averaged over the runs, decreases as the number of episodes TT grows, which is consistent with the regret bounds.

In this experiment, the preferences at one state change three times during the run, so that the best pair at this state differs between periods, and the transitions at this state are stochastic. Under known transitions, the regret is within 9% of that with fixed preferences in Figure 3. Under unknown transitions, it is at most 38% larger than under known transitions.

The experiments of the submitted version (Appendices G.2 to G.4) use the instances of the lower-bound analysis because the regret lower bound can be computed explicitly for them and compared with the measured regret, as in Figure 3. Appendix G of the revised version mentions this (Lines 2488–2489).

Transitions that depend on the observed preference outcome (W2, Q2)

The framework assumes that future states depend on the pair of arms presented, rather than on which arm is actually preferred. [...] How would the proposed framework and its theoretical guarantees change if future state transitions depended on the observed preference outcome rather than only on the compared pair?

If the next state depends on which arm is preferred, our regret bounds for unknown transitions remain valid when the preferences do not change across episodes. When the preferences change, our guarantees do not apply.

To see this, let Pt(s,(i,j))\mathsf P_t(s,(i,j)) denote, as in the paper, the probability that arm ii is preferred to arm jj at state ss in episode tt. Suppose that the next state is drawn from a distribution Pitem(⋅∣s,i)P^{\mathrm{item}}(\cdot\mid s,i) if arm ii is preferred. After the pair (i,j)(i,j) is displayed at state ss, the next state then has the distribution Pt(s,(i,j))Pitem(⋅∣s,i)+(1−Pt(s,(i,j)))Pitem(⋅∣s,j).\mathsf P_t(s,(i,j))P^{\mathrm{item}}(\cdot\mid s,i)+\bigl(1-\mathsf P_t(s,(i,j))\bigr)P^{\mathrm{item}}(\cdot\mid s,j). Note that Pt\mathsf P_t is a preference probability, whereas PitemP^{\mathrm{item}} is a distribution over next states.

If Pt\mathsf P_t is the same in every episode tt, this distribution is also the same in every episode. The next state then follows a fixed transition kernel that depends only on the displayed pair, as our model assumes. The kernel is unknown to the learner, since it involves Pt\mathsf P_t. Then, the regret bounds for unknown transitions (Theorems 8 and 17) hold with the same proofs, which do not use the independence of the comparison outcome and the next state given the displayed pair.

If Pt\mathsf P_t changes across episodes, this distribution changes with it, whereas our analysis requires a fixed transition kernel. For general MDPs with bandit feedback whose transitions change adversarially, it is known that sublinear regret is possible only with an exponential dependence on the episode length (see Jin et al., "No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions", NeurIPS 2023, and the references therein). In the present case, the transitions change only through Pt\mathsf P_t, and we do not know whether this structure allows guarantees comparable to ours. The conclusion of the revised version mentions this extension as future work (Lines 488–491).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We sincerely thank all reviewers for taking the time to carefully review our paper and for their comments. Our responses to each reviewer are posted separately. In the revised PDF, the changes made in response to the reviews are marked in dark blue, and the main ones are listed below.

  1. A new experiment evaluates global optimization and policy optimization with changing preferences, under both known and unknown transitions (Appendix G.5 and Figure 6), and the introduction summarizes its result (in response to Reviewer LT3C).
  2. The introduction now states that policy optimization has a shorter running time per episode at the cost of a larger regret (in response to Reviewer e6VT).
  3. The introduction now states the regret bounds for unknown transitions with their S4S^4 terms (in response to Reviewer e6VT).
  4. The introduction now explains in more detail why policy optimization with preference feedback requires a new estimator of the Q-function (in response to Reviewer 7rvg).
  5. The conclusion now mentions as future work the extension to transitions that depend on the preference outcome when the preferences change (in response to Reviewers LT3C and e6VT).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.