Pith. sign in

REVIEW 1 major objections 5 minor 54 references

Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that outcome-based online reinforcement learning with general function approximation is sample-efficient under coverability and Bellman completeness, while also proving an exponential separation from per-step reward…

desk verdict Settles the sample complexity of outcome-based online RL under general function approximation, with an exponential separation lower bound; the flagged proposition issue is a typo, not a gap. read the letter →

arxiv 2505.20268 v2 pith:SUKGKFOJ submitted 2025-05-26 cs.LG cs.AImath.STstat.MLstat.TH

Fan Chen , Zeyu Jia , Alexander Rakhlin , Tengyang Xie This is my paper
classification cs.LGcs.AImath.STstat.MLstat.TH MSC 68Q3290C40
keywords outcome-basedreinforcementlearningtrajectoryfeedbackgeneralfunctionapproximationcoverabilityBellmancompletenesssamplecomplexitypreference-basedRLexponentialseparation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Reinforcement learning usually hands the agent a reward after every action; this paper studies the harder setting where only one total reward arrives after a whole trajectory ends, as in human feedback on a generated text or a clinical outcome after a treatment. The paper's central claim is that this collapsed feedback is still enough for sample-efficient online exploration with rich function approximation, provided the MDP is coverable and the function classes satisfy realizability and Bellman completeness; its main algorithm reaches an $\epsilon$-optimal policy in $\widetilde{O}(C_{\rm cov} H^3/\epsilon^2)$ episodes. The paper also proves that this tractability has a boundary: for a horizon-2 MDP family with $d$-dimensional generalized linear rewards, per-step rewards are learnable in $\widetilde{O}(d^2/\epsilon^2)$ episodes while outcome-only rewards force $e^{\Omega(d)}$ episodes. A sympathetic reader would care because the result delineates when credit assignment is a nuisance that can be engineered around and when it is a genuine statistical wall.

What carries the argument

The load-bearing object is the joint optimistic objective in Equation (6): the algorithm maximizes $\lambda$ times the initial-state value minus two empirical losses — the Bellman loss $L^{\rm BE}_D(f;R)$, which measures squared violation of the Bellman equation under a proxy reward model with the infimum over a comparator class subtracted to avoid double sampling, and the reward-model loss $L^{\rm RM}_D(R)$ on (trajectory, outcome) pairs. Coverability $C_{\rm cov}$, the worst-case density ratio between any policy's state-action occupancy and a shared measure, controls the distribution shift in the coverability argument. The key technical identity is Proposition 15, which bounds per-step reward discrepancies by trajectory-level squared errors under the layer-wise exploration policies $\pi \circ_h \pi_{\rm ref}$, allowing outcome-only data to drive the step-level analysis. For deterministic MDPs, the Bellman residual $R_f(\tau)=\sum_{h}[f_h(s_h,a_h)-f_{h+1}(s_{h+1})]$ becomes an exact reward model, removing the need for a reward class and a comparator class.

What would settle it

Construct the two-state, two-action MDP from Proposition 23, run Algorithm 4 (reward model fitted first, then GOLF) and record the action distribution at state $s_2$: the argument predicts the algorithm never selects $a_1$ and stays at least 0.01-suboptimal after any number of rounds. To test the lower bound directly, build the horizon-2 MDP of Theorem 4 with large $d$ and measure the number of outcome-reward episodes any algorithm needs to reach 0.1-optimality; the theorem requires $e^{\Omega(d)}$, so a poly($d$) algorithm would refute it.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that outcome-based online RL with general function approximation is PAC-learnable: Algorithm 1, which jointly maximizes a value function and a reward model against a subtracted Bellman-loss baseline over a comparator class, returns an $\epsilon$-optimal policy with high probability using $\widetilde{O}(C_{\rm cov} H^3/\epsilon^2)$ episodes under realizability and Bellman completeness, where $C_{\rm cov}$ is the coverability coefficient of the MDP. The same framework transfers to preference feedback under the Bradley-Terry-Luce model with equivalent sample complexity. Complementing this positive result, the paper constructs a two-layer generalized-linear MDP class on which process reward is easy ($\widetilde{O}(d^2/\epsilon^2)$ episodes) but outcome reward is exponentially hard ($\Omega(e^d)$ episodes), proving that trajectory-level feedback is not statistically equivalent to per-step feedback in general. For deterministic transitions, a simpler Bellman-residual algorithm (Algorithm 2) achieves a similar guarantee using only realizability, and a decoupled reward-model-first approach is shown to fail on a constructed MDP.

Load-bearing premise

The main algorithm's guarantee rests on Bellman completeness (Assumption 2): for every value function in $F$ and every reward model in $R$, the one-step backup $T_{R,h} f_{h+1}$ must be approximately representable in the comparator class $G_h$. If this fails, the uniform-concentration step that turns empirical Bellman loss into population error collapses, and the sample-complexity bound in Theorem 1 no longer follows.

Editorial extensions

If this is right

  • Outcome-based online RL with general function approximation is PAC-learnable whenever the MDP has bounded coverability and the function classes are realizable and Bellman-complete, with the same $C_{\rm cov}$ dependence as process-reward algorithms up to an extra $\widetilde{O}(H)$ factor.
  • Learning a reward model first and then optimizing the value function is provably insufficient: the joint optimization in Algorithm 1 is necessary in the worst case (Proposition 23).
  • For deterministic MDPs, the completeness assumption can be dropped entirely; a simpler Bellman-residual maximizer achieves the same style of guarantee.
  • Preference feedback under the Bradley-Terry-Luce model inherits the same statistical efficiency as outcome rewards, so the algorithmic template covers RLHF-style comparisons.
  • Statistically, outcome feedback and per-step feedback are not equivalent: there are structured two-layer MDPs where per-step learning is polynomial but outcome-only learning is exponential, so any credit-assignment shortcut must exploit more than smooth reward structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exponential separation suggests that intermediate supervision at a few selected time steps, rather than at every step, could interpolate between the two extremes; a testable extension is whether sparse per-step rewards at $O(\log d)$ checkpoints remove the exponential gap.
  • The joint-optimization necessity result implies that pipeline architectures in RLHF that freeze a trained reward model before optimizing the policy may inherit the hardness of the decoupled approach, even when a joint objective would be tractable.
  • Because the lower bound uses only known transitions and horizon 2, model-based planning would not obviously bypass the outcome-reward hardness; verifying whether a model-based algorithm with a learned transition also needs $e^{\Omega(d)}$ episodes is a natural next check.
  • The preference-based extension inherits the same Bellman-completeness dependence, suggesting that any hardness in outcome-based learning appears in preference-based learning as well — a claim the paper does not state explicitly.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper studies online reinforcement learning with outcome-based feedback, where the learner observes only a single trajectory-level reward rather than per-step rewards. It proposes Algorithm 1, a model-free optimistic algorithm that jointly optimizes over a value-function class and a reward-function class, and claims a sample complexity of order eO(Ccov H^3/epsilon^2) under realizability and Bellman completeness (Theorem 1). For deterministic MDPs, Algorithm 2 is claimed to achieve a similar guarantee under only realizability (Theorem 2). The paper also extends the approach to preference-based feedback under the Bradley-Terry-Luce model (Theorem 3) and proves an exponential statistical separation between outcome-based and per-step feedback for a class of horizon-2 generalized-linear MDPs (Theorem 4). The appendix contains detailed proofs, uniform-concentration lemmas, and a hardness example for decoupled reward fitting.

Significance. If the technical issues are fixed, this is a valuable contribution: it is the first general-function-approximation treatment of online RL with outcome-based rewards, and its upper bound matches the GOLF-style coverability rate up to a factor of H. The deterministic-MDP simplification and the preference-based extension broaden the applicability of the framework, and the lower bound identifies a concrete structural barrier that separates outcome feedback from process feedback. The proofs are detailed and largely coherent, and the reliance on coverability rather than reward-specific structure is a strength. The main caveat is a local but load-bearing mismatch in the proof of Theorem 1, described below.

major comments (1)
  1. [Appendix C.1, Proposition 12 and proof of Theorem 1] Proposition 12 defines the Bellman error as e_h^{(t)} := f_h^{(t)} - T^*_h f_{h+1}^{(t)}, but the performance-difference decomposition (17) and the subsequent display (18) require e_h^{(t)} := f_h^{(t)} - T_{R^{(t)},h} f_{h+1}^{(t)}. The only uniform concentration available from Lemma 17 is for squared errors involving T_{R,h}, not T^*_h, so Proposition 12 as stated cannot be invoked on the first summation in (18). As written, the proof of Theorem 1 has a missing link at the point where the main sample-complexity bound is derived. Please restate Proposition 12 with the T_{R^{(t)}} operator and verify that the proof of Theorem 1 closes with that definition.
minor comments (5)
  1. [Section F.2, proof of Theorem 4] The displayed expectation E[R|pi] = (1/4) ReLU(<a_pi,v> - b) + 1/2 contradicts the immediately preceding Bernoulli law R|tau_pi ~ Bern((1/3) ReLU(<a_pi,v> - b) + 2/3) and the stated form J(pi) = 2/3 + (epsilon/3) 1{a_pi = v}. The constants should be 1/3 and 2/3.
  2. [Appendix D, proof of Theorem 2] In the optimism step, the displayed inequality lambda f^(t)_1(s^(t)_1) - LBR_{D(t-1)}(f^(t)) >= lambda V^sharp_1(s^(t)_1) - LBR_{D(t-1)}(f^(t)) has the same loss on both sides and is content-free; the right-hand side should involve LBR_{D(t-1)}(Q^sharp). A few lines later, LBE_{D(t-1)}(Q^sharp) should be LBR_{D(t-1)}(Q^sharp).
  3. [Appendix C.3, proof of Lemma 17] The sentence 'we only need to note that G_h subset of F_h' contradicts Assumption 2, which states F_h subset of G_h; the covering argument should use the stated inclusion.
  4. [Section F.1, proof of Proposition 23] The claim that for any trajectory tau = (s1, a~1, s2, a~2) with outcome reward r = R1(s1,a~1)+R1(s2,a~2) it always holds that r = R2(s1)+R2(s2,a~2) is false when the second action is a1; the equality holds only for trajectories the algorithm actually collects, namely those taking a2 at s2. Please restate the claim conditionally.
  5. [Algorithm 3, paragraph before Theorem 3] The sentence 'Execute pi^(t) circ_h pi_ref for two episode' contains a grammatical error and should read 'for two episodes'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper and lower bounds are conditional derivations from stated assumptions, not restatements of their inputs.

full rationale

I walked the paper's derivation chain and found no step where a claimed prediction or first-principles result reduces, by the paper's own equations or by self-citation, to its input. Theorem 1 is explicitly conditional on realizability (Assumption 1) and Bellman completeness (Assumption 2); Algorithm 1 optimizes a joint value/reward objective, and the proof decomposes the performance difference into value Bellman errors and reward-model errors. Those are bounded by uniform-concentration lemmas (Propositions 11, 16, 17) and coverability/elliptical-potential arguments (Propositions 12-15), with constants depending on the assumed function classes, the horizon, and the coverability coefficient Ccov. The conclusion is not an identity with the assumptions: the sample-complexity bound is a derived consequence of them. The self-citations that appear are not load-bearing in a circular way. Coverability is taken from Xie et al. (2022) and Proposition 14 is credited to that line of work, but both are stated technical tools rather than the paper's target result. Proposition 13 is said to be 'inspired by' Jia et al. (2025), but the actual bound is proved in this paper via Proposition 15 and the coverability argument; no unproved conclusion is imported. Theorem 4's lower bound is established by a concrete packing construction and a reduction to multi-arm bandits / ReLU bandit hardness, not by assuming the separation. The possible mismatch between the Bellman operator in Proposition 12 and the operator appearing in the Theorem 1 proof is a proof-correctness concern, not a circularity concern. Therefore the appropriate finding is no significant circularity.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard RL assumptions (realizability, completeness, determinism for one variant, and BTL preferences) rather than on fitted constants or new entities. The only hand-set quantities are the algorithm hyperparameter lambda and the assumed approximation error eps_app. No new particles, forces, or mediators are introduced.

free parameters (2)
  • optimism weight lambda = c0 max(H log(N_T H^2 / delta) / eps, T H eps_app); analogous choices in Theorems 2 and 3
    Hyperparameter in the optimistic objective, Equations (6), (9), and (12). It is set from quantities in the theorem, not fitted to data, but the final sample complexity depends on this choice.
  • approximation error eps_app = fixed nonnegative constant
    Measures how far the function classes are from exact realizability and completeness. The theorem states degradation in terms of eps_app; it is an assumed error level, not estimated from data.
assumptions (5)
  • domain assumption Realizability (Assumption 1): value and reward classes contain functions within eps_app of Q* and R*
    Invoked throughout Theorems 1 and 3 to ensure the optimistic search space contains near-optimal candidates.
  • domain assumption Bellman completeness (Assumption 2): the comparator class G approximately contains Bellman backups of F under any R in the reward class
    Used in Lemma 17 and Theorem 1 to control the Bellman loss via uniform concentration.
  • domain assumption Deterministic transitions (Assumptions 3 and 4) for Algorithm 2
    Guarantees the value-difference reward identity used in Bellman residual minimization.
  • domain assumption Bradley-Terry-Luce comparison model (Definition 3) for preference feedback
    Defines the statistical model under which Theorem 3 is proved.
  • standard math Standard concentration and packing results, including Freedman's inequality, union bounds, elliptical potential arguments, and sphere packing
    Used without proof in the appendix derivations; they are standard tools in online learning theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits." pith.science (2026). https://pith.science/paper/SUKGKFOJ

@misc{pith2026250520268,
  author       = {Pith},
  title        = {Pith review of: Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SUKGKFOJ}},
  note         = {Machine review of arXiv:2505.20268}
}
abstract

Reinforcement learning with outcome-based feedback faces a fundamental challenge: when rewards are only observed at trajectory endpoints, how do we assign credit to the right actions? This paper provides the first comprehensive analysis of this problem in online RL with general function approximation. We develop a provably sample-efficient algorithm achieving $\widetilde{O}({C_{\rm cov} H^3}/{\epsilon^2})$ sample complexity, where $C_{\rm cov}$ is the coverability coefficient of the underlying MDP. By leveraging general function approximation, our approach works effectively in large or infinite state spaces where tabular methods fail, requiring only that value functions and reward functions can be represented by appropriate function classes. Our results also characterize when outcome-based feedback is statistically separated from per-step rewards, revealing an unavoidable exponential separation for certain MDPs. For deterministic MDPs, we show how to eliminate the completeness assumption, dramatically simplifying the algorithm. We further extend our approach to preference-based feedback settings, proving that equivalent statistical efficiency can be achieved even under more limited information. Together, these results constitute a theoretical foundation for understanding the statistical properties of outcome-based reinforcement learning.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

54 extracted references · 29 canonical work pages

  1. [1]

    Harnessing density ratios for online reinforcement learning

    Philip Amortila, Dylan J Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforcement learning. arXiv preprint arXiv:2401.09681, 2024 a

    arXiv 2024

  2. [2]

    Scalable online exploration via coverability

    Philip Amortila, Dylan J Foster, and Akshay Krishnamurthy. Scalable online exploration via coverability. arXiv preprint arXiv:2403.06571, 2024 b

    arXiv 2024

  3. [3]

    Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path

    Andr \'a s Antos, Csaba Szepesv \'a ri, and R \'e mi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71: 0 89--129, 2008

    work page 2008

  4. [4]

    Training a helpful and harmless assistant with reinforcement learning from human feedback

    Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022

    arXiv 2022

  5. [5]

    Contextual bandit algorithms with supervised learning guarantees

    Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19--26. JMLR Workshop and Conference Proceedings, 2011

    work page 2011

  6. [6]

    Adversarial model for offline reinforcement learning

    Mohak Bhardwaj, Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023

    work page 2023

  7. [7]

    Rank analysis of incomplete block designs: I

    Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39 0 (3/4): 0 324--345, 1952

    1952

  8. [8]

    Near-optimal regret in linear mdps with aggregate bandit feedback

    Asaf Cassel, Haipeng Luo, Aviv Rosenberg, and Dmitry Sotnikov. Near-optimal regret in linear mdps with aggregate bandit feedback. arXiv preprint arXiv:2405.07637, 2024

    arXiv 2024

Show all 54 references
  1. [9]

    Value-incentivized preference optimization: A unified approach to online and offline rlhf

    Shicong Cen, Jincheng Mei, Katayoon Goshvadi, Hanjun Dai, Tong Yang, Sherry Yang, Dale Schuurmans, Yuejie Chi, and Bo Dai. Value-incentivized preference optimization: A unified approach to online and offline rlhf. arXiv preprint arXiv:2405.19320, 2024

    2024 arXiv

  2. [10]

    On the theory of reinforcement learning with once-per-episode feedback

    Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with once-per-episode feedback. Advances in Neural Information Processing Systems, 34: 0 3401--3412, 2021

    2021

  3. [11]

    Unified algorithms for rl with decision-estimation coefficients: pac, reward-free, preference-based learning, and beyond

    Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-estimation coefficients: pac, reward-free, preference-based learning, and beyond. arXiv preprint arXiv:2209.11745, 2022 a

    2022 arXiv

  4. [12]

    Near-optimal learning and planning in separated latent mdps

    Fan Chen, Constantinos Daskalakis, Noah Golowich, and Alexander Rakhlin. Near-optimal learning and planning in separated latent mdps. In The Thirty Seventh Annual Conference on Learning Theory, pages 995--1067. PMLR, 2024

    2024

  5. [13]

    Information-theoretic considerations in batch reinforcement learning

    Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042--1051. PMLR, 2019

    2019

  6. [14]

    Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation

    Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773--3793. PMLR, 2022 b

    2022

  7. [15]

    Stochastic linear optimization under bandit feedback

    Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In 21st Annual Conference on Learning Theory, number 101, pages 355--366, 2008

    2008

  8. [16]

    Provably sample efficient rlhf via active preference optimization

    Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rlhf via active preference optimization. arXiv preprint arXiv:2402.10500, 2024

    2024 arXiv

  9. [17]

    Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature

    Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. Advances in Neural Information Processing Systems, 34: 0 26168--26182, 2021

    2021

  10. [18]

    Bilinear classes: A structural framework for provable generalization in rl

    Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826--2836. PMLR, 2021

    2021

  11. [19]

    Reinforcement learning with trajectory feedback

    Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7288--7295, 2021

    2021

  12. [20]

    Error propagation for approximate policy and value iteration

    Amir-massoud Farahmand, Csaba Szepesv \'a ri, and R \'e mi Munos. Error propagation for approximate policy and value iteration. Advances in neural information processing systems, 23, 2010

    2010

  13. [21]

    The statistical complexity of interactive decision making

    Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021

    2021 arXiv

  14. [22]

    On the complexity of adversarial decision making

    Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35: 0 35404--35417, 2022

    2022

  15. [23]

    Openai o1 system card

    Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024

    2024 arXiv

  16. [24]

    Do we need to verify step by step? rethinking process supervision from a theoretical perspective

    Zeyu Jia, Alexander Rakhlin, and Tengyang Xie. Do we need to verify step by step? rethinking process supervision from a theoretical perspective. arXiv preprint arXiv:2502.10581, 2025

    2025 arXiv

  17. [25]

    Contextual decision processes with low bellman rank are pac-learnable

    Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704--1713. PMLR, 2017

    2017

  18. [26]

    Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms

    Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34: 0 13406--13418, 2021 a

    2021

  19. [27]

    Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084--5096

    Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084--5096. PMLR, 2021 b

    2021

  20. [28]

    Approximately optimal approximate reinforcement learning

    Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pages 267--274, 2002

    2002

  21. [29]

    Near-optimal regret using policy optimization in online mdps with aggregate bandit feedback

    Tal Lancewicki and Yishay Mansour. Near-optimal regret using policy optimization in online mdps with aggregate bandit feedback. arXiv preprint arXiv:2502.04004, 2025

    2025 arXiv

  22. [30]

    Bandit algorithms

    Tor Lattimore and Csaba Szepesv \'a ri. Bandit algorithms. Cambridge University Press, 2020

    2020

  23. [31]

    Understanding the eluder dimension

    Gene Li, Pritish Kamath, Dylan J Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35: 0 23737--23750, 2022

    2022

  24. [32]

    What can online reinforcement learning with function approximation benefit from general coverage conditions? In International Conference on Machine Learning, pages 22063--22091

    Fanghui Liu, Luca Viano, and Volkan Cevher. What can online reinforcement learning with function approximation benefit from general coverage conditions? In International Conference on Machine Learning, pages 22063--22091. PMLR, 2023

    2023

  25. [33]

    Error bounds for approximate policy iteration

    R \'e mi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560--567. Citeseer, 2003

    2003

  26. [34]

    An efficient algorithm for learning with semi-bandit feedback

    Gergely Neu and G \'a bor Bart \'o k. An efficient algorithm for learning with semi-bandit feedback. In International Conference on Algorithmic Learning Theory, pages 234--248. Springer, 2013

    2013

  27. [35]

    Dueling posterior sampling for preference-based reinforcement learning

    Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029--1038. PMLR, 2020

    2020

  28. [36]

    Model-based reinforcement learning and the eluder dimension

    Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, volume 27, pages 1466--1474, 2014

    2014

  29. [37]

    Training language models to follow instructions with human feedback

    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, 35: 0 2...

    2022

  30. [38]

    Dueling rl: reinforcement learning with trajectory preferences

    Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850, 2021

    2021 arXiv

  31. [39]

    Eluder dimension and the sample complexity of optimistic exploration

    Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, volume 26, pages 2256--2264, 2013

    2013

  32. [40]

    Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches

    Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898--2933. PMLR, 2019

    2019

  33. [41]

    Reinforcement learning: An introduction, volume 1

    Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998

    1998

  34. [42]

    Is rlhf more difficult than standard rl? arXiv preprint arXiv:2306.14111, 2023

    Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rl? arXiv preprint arXiv:2306.14111, 2023

    2023 arXiv

  35. [43]

    Making rl with preference-based feedback efficient via randomization

    Runzhe Wu and Wen Sun. Making rl with preference-based feedback efficient via randomization. arXiv preprint arXiv:2310.14554, 2023

    2023 arXiv

  36. [44]

    Batch value-function approximation with only realizability

    Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11404--11413. PMLR, 2021

    2021

  37. [45]

    Bellman-consistent pessimism for offline reinforcement learning

    Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34: 0 6683--6694, 2021

    2021

  38. [46]

    The role of coverage in online reinforcement learning

    Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04157, 2022

    2022 arXiv

  39. [47]

    Exploratory preference optimization: Harnessing implicit q*-approximation for sample-efficient rlhf

    Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q*-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.21046, 2024

    2024 arXiv

  40. [48]

    Preference-based reinforcement learning with finite-time guarantees

    Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33: 0 18784--18794, 2020

    2020

  41. [49]

    A theoretical analysis of nash learning from human feedback under general kl-regularized preference

    Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314, 2024

    2024 arXiv

  42. [50]

    Learning near optimal policies with low inherent bellman error

    Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978--10989. PMLR, 2020

    2020

  43. [51]

    Provable offline preference-based reinforcement learning

    Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline preference-based reinforcement learning. arXiv preprint arXiv:2305.14816, 2023

    2023 arXiv

  44. [52]

    Self-exploring language models: Active preference elicitation for online alignment

    Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong, Zhihan Liu, Ziyi Yang, Shuohang Wang, Hany Hassan, and Zhaoran Wang. Self-exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405.19332, 2024

    2024 arXiv

  45. [53]

    Covering number bounds of certain regularized linear function classes

    Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2 0 (Mar): 0 527--550, 2002

    2002

  46. [54]

    Principled reinforcement learning with human feedback from pairwise or k-wise comparisons

    Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning, pages 43037--43067. PMLR, 2023

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.