- 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 , where , , , and 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 , and extend both guarantees to unknown transitions. The authors finally establish a lower bound of .
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.
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 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/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.
We have added the comparison for policy optimization to the introduction, with a reference to Section 5.1 (Lines 89–94).