Pith. sign in

REVIEW 1 major objections 1 minor 89 references

Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

T0 review · 1 major / 1 minor · reviewed 2026-07-01 · grok-4.3

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

Pith's one-line read Policy optimization achieves first-order and second-order regret bounds in MDPs with unknown transitions

desk verdict They close the known-transition gap for data-dependent PO bounds by adding a loss-prediction bonus, but the bias-control step in the optimistic estimators is the part that still needs checking. read the letter →

arxiv 2606.31769 v1 pith:5BAJN34O submitted 2026-06-30 cs.LG stat.ML

Mingyi Li , Taira Tsuchiya , Kenji Yamanishi This is my paper · ORCID
classification cs.LGstat.ML
keywords policyoptimizationregretboundsMarkovdecisionprocessesunknowntransitionsdata-dependentfollow-the-regularized-leaderonlinelearningQ-functionestimators
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

The paper shows that policy optimization can achieve data-dependent regret bounds in online episodic tabular MDPs even when the transition kernel is unknown, closing an open question from prior work that required known transitions. It does so by introducing an algorithm based on optimistic follow-the-regularized-leader that uses new optimistic Q-function estimators and a data-dependent transition bonus to control bias via loss-prediction error. This produces the first-order, second-order, and path-length bounds, an additional transition-dependent complexity term, and gap-dependent polylog(T) regret in stochastic cases. A reader would care if true because it makes adaptive regret analysis applicable to more realistic MDPs where transitions must be learned from interaction data.

What carries the argument

optimistic Q-function estimators with a data-dependent transition bonus that controls bias through loss-prediction error in an optimistic follow-the-regularized-leader algorithm

What would settle it

Finding an MDP with unknown transitions where the optimistic Q-estimators without the data-dependent bonus violate the first-order regret bound would falsify the sufficiency of the design.

Watch

Extended reading notes

Core claim

The paper develops a new algorithm based on optimistic follow-the-regularized-leader that attains first-order, second-order, and path-length bounds under unknown transitions. The key ingredient is a new design of optimistic Q-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. The analysis identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel, yielding the bounds with this term while achieving gap-dependent polylog(T) regret in the stochastic regime.

Load-bearing premise

The data-dependent transition bonus constructed from loss-prediction error is sufficient to control the bias in the optimistic Q-function estimators without introducing terms that invalidate the regret bounds.

Editorial extensions

If this is right

  • The new algorithm attains first-order, second-order, and path-length regret bounds with unknown transitions.
  • An unavoidable transition-dependent complexity term is identified in the bounds.
  • Gap-dependent polylog(T) regret is achieved in the stochastic regime.
  • The guarantees hold for both adversarial and stochastic loss sequences.

Reading between the lines

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

  • The transition-dependent complexity term being unavoidable indicates an intrinsic cost to learning dynamics that any algorithm must pay in some form.
  • The bias control mechanism via loss-prediction error may be adaptable to other online learning problems involving estimation of unknown parameters.
  • These results suggest that data-dependent analysis can be extended to broader classes of MDPs if similar bias-correction techniques are developed.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 1 minor

Summary. The paper claims to develop a new optimistic follow-the-regularized-leader algorithm for policy optimization in online episodic tabular MDPs with unknown transition kernels. Using novel optimistic Q-function estimators paired with a data-dependent transition bonus constructed from loss-prediction error, the algorithm attains first-order, second-order, and path-length regret bounds (augmented by an unavoidable transition-dependent complexity term) while also achieving gap-dependent polylog(T) regret in the stochastic regime, thereby extending known-transition data-dependent guarantees to the unknown-transition setting.

Significance. If the central analysis holds, the result is significant: it closes an open question on whether policy optimization can achieve best-of-both-worlds data-dependent bounds without known transitions, and the explicit isolation of the transition complexity term clarifies the intrinsic cost of kernel estimation. The work builds directly on Dann et al. (2023) and Li et al. (2026) and supplies a concrete algorithmic design that could influence practical RL algorithms requiring adaptation to both adversarial and stochastic losses.

major comments (1)
  1. [Analysis of Q-estimators and transition bonus] The section describing the optimistic Q-function estimators and transition bonus (the key ingredient highlighted in the abstract): the claim that the data-dependent transition bonus, built from loss-prediction error, controls bias in the optimism step without introducing extra additive or multiplicative factors (e.g., scaling with visit counts or |S|×|A|) must be verified in the regret decomposition. If this cancellation fails, the first-order/second-order/path-length bounds would acquire additional terms that prevent the claimed adaptation to adversarial and stochastic losses.
minor comments (1)
  1. [Abstract] The abstract states that the analysis 'identifies an unavoidable transition-dependent complexity term' but does not give its explicit form; adding a brief expression or scaling (e.g., in terms of |S|, |A|, or covering numbers) would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the central technical point in our analysis. We address the major comment below.

read point-by-point responses

  1. Referee: [Analysis of Q-estimators and transition bonus] The section describing the optimistic Q-function estimators and transition bonus (the key ingredient highlighted in the abstract): the claim that the data-dependent transition bonus, built from loss-prediction error, controls bias in the optimism step without introducing extra additive or multiplicative factors (e.g., scaling with visit counts or |S|×|A|) must be verified in the regret decomposition. If this cancellation fails, the first-order/second-order/path-length bounds would acquire additional terms that prevent the claimed adaptation to adversarial and stochastic losses.

    Authors: We appreciate the referee drawing attention to this key step. In the regret decomposition (Section 4, Theorem 1, and the full proof in Appendix B), the transition bonus is defined directly from the per-state-action loss-prediction error of the optimistic Q-estimator. This construction ensures that the bias introduced by the unknown transition kernel is exactly offset by the bonus term inside the optimism inequality. Because the bonus scales with the same data-dependent quantities already appearing in the known-transition analysis of Dann et al. (2023) and Li et al. (2026), no additional multiplicative factors in visit counts or additive |S|×|A| terms arise. The only extra term that survives is the unavoidable transition-dependent complexity that we isolate explicitly. The cancellation is therefore verified in the existing proof and preserves the first-order, second-order, and path-length bounds (augmented solely by the transition term) as well as the polylog(T) stochastic bound. revision: no

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; derivation self-contained against external benchmarks

full rationale

The provided abstract and description introduce a new optimistic FTRL algorithm with custom Q-estimators and a transition bonus derived from loss-prediction error. No equations are exhibited that reduce a claimed prediction or bound to a fitted parameter or self-citation by construction. The transition-dependent complexity term is explicitly identified as unavoidable and separate from the data-dependent bounds, indicating the central claim rests on independent analysis rather than tautological re-labeling of inputs. Self-citations to prior work on known transitions are not load-bearing for the unknown-transition extension.

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

Abstract-only review; no access to full derivations, so free parameters, axioms, and invented entities cannot be enumerated. The central claim appears to rest on the existence of a bias-controlling transition bonus whose construction is not detailed here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions." pith.science (2026). https://pith.science/paper/5BAJN34O

@misc{pith2026260631769,
  author       = {Pith},
  title        = {Pith review of: Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5BAJN34O}},
  note         = {Machine review of arXiv:2606.31769}
}
abstract

We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic $Q$-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent $\mathrm{polylog}(T)$ regret in the stochastic regime.

Figures

Figures reproduced from arXiv: 2606.31769 by the authors.

Figure 1
Figure 1. Definitions of the Q-function estimator Qbt, the learning-rate update ηt+1, and the local exploration bonus bt used in Algorithm 1. Yt = 0, make episode t virtual, and shift the indices of all subsequent real episodes. The algorithm then uses the zero loss function and only updates the pair (s † t , a † t ) ∈ arg maxs,a ηt(s, a)/qt(s), multiplying 1/ηt(s † t , a † t ) by 1+ 1 324H log(T) . It still computes Qbt, bt,… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

89 extracted references · 89 canonical work pages

  1. [1]

    International Conference on Machine Learning , pages=

    Best of both worlds policy optimization , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    work page 2023

  2. [2]

    Conference on Learning Theory , pages=

    Adversarially robust multi-armed bandit algorithm with variance-dependent regret bounds , author=. Conference on Learning Theory , pages=. 2022 , organization=

    work page 2022

  3. [3]

    Near-optimal Regret Using Policy Optimization in Online

    Lancewicki, Tal and Mansour, Yishay , booktitle =. Near-optimal Regret Using Policy Optimization in Online. 2025 , volume =

    work page 2025

  4. [4]

    Proceedings of the 41st International Conference on Machine Learning , pages=

    More benefits of being distributional: second-order bounds for reinforcement learning , author=. Proceedings of the 41st International Conference on Machine Learning , pages=

    work page

  5. [5]

    International Conference on Machine Learning , pages=

    Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    work page 2019

  6. [6]

    Proceedings of the 34th International Conference on Machine Learning , pages =

    Minimax Regret Bounds for Reinforcement Learning , author =. Proceedings of the 34th International Conference on Machine Learning , pages =. 2017 , volume =

    work page 2017

  7. [7]

    Proceedings of Thirty Fourth Conference on Learning Theory , pages =

    Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon , author =. Proceedings of Thirty Fourth Conference on Learning Theory , pages =. 2021 , volume =

    work page 2021

  8. [8]

    International Conference on Machine Learning , pages=

    Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    work page 2023

Show all 89 references
  1. [9]

    Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular

    Shulun Chen and Runlong Zhou and Zihan Zhang and Maryam Fazel and Simon Shaolei Du , booktitle =. Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular

  2. [10]

    Non-Asymptotic Gap-Dependent Regret Bounds for Tabular

    Simchowitz, Max and Jamieson, Kevin G , booktitle =. Non-Asymptotic Gap-Dependent Regret Bounds for Tabular

  3. [11]

    Online learning in episodic

    Zimin, Alexander and Neu, Gergely , booktitle =. Online learning in episodic

  4. [12]

    Jin, Chi and Allen-Zhu, Zeyuan and Bubeck, Sebastien and Jordan, Michael I , booktitle =. Is

  5. [13]

    Learning Adversarial

    Jin, Chi and Jin, Tiancheng and Luo, Haipeng and Sra, Suvrit and Yu, Tiancheng , booktitle =. Learning Adversarial. 2020 , volume =

    2020

  6. [14]

    Policy Optimization in Adversarial

    Luo, Haipeng and Wei, Chen-Yu and Lee, Chung-Wei , booktitle =. Policy Optimization in Adversarial

  7. [15]

    Tsybakov, Alexandre B , title =

  8. [16]

    Laurent and P

    B. Laurent and P. Massart , journal =. Adaptive Estimation of a Quadratic Functional by Model Selection , volume =

  9. [17]

    Refined Lower Bounds for Adversarial Bandits , volume =

    Gerchinovitz, S\'. Refined Lower Bounds for Adversarial Bandits , volume =. Advances in Neural Information Processing Systems , pages =

  10. [18]

    Probability and Mathematical Statistics , volume=

    Inequalities for quantiles of the chi-square distribution , author=. Probability and Mathematical Statistics , volume=. 2010 , publisher=

    2010

  11. [19]

    2013 , month =

    Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal , title =. 2013 , month =

    2013

  12. [20]

    Tuning Bandit Algorithms in Stochastic Environments

    Audibert, Jean-Yves and Munos, R \'e mi and Szepesv \'a ri, Csaba. Tuning Bandit Algorithms in Stochastic Environments. Algorithmic Learning Theory. 2007

    2007

  13. [21]

    Online Convex Optimization in Adversarial

    Rosenberg, Aviv and Mansour, Yishay , booktitle =. Online Convex Optimization in Adversarial. 2019 , volume =

    2019

  14. [22]

    Proceedings of the 37th International Conference on Machine Learning , pages =

    Optimistic Policy Optimization with Bandit Feedback , author =. Proceedings of the 37th International Conference on Machine Learning , pages =. 2020 , volume =

    2020

  15. [23]

    Even-Dar, Eyal and Kakade, Sham M and Mansour, Yishay , journal=. Online. 2009 , publisher=

    2009

  16. [24]

    Online Markov Decision Processes under Bandit Feedback , volume =

    Neu, Gergely and Antos, Andras and Gy\". Online Markov Decision Processes under Bandit Feedback , volume =. Advances in Neural Information Processing Systems , pages =

  17. [25]

    Learning adversarial

    Lancewicki, Tal and Rosenberg, Aviv and Mansour, Yishay , booktitle=. Learning adversarial

  18. [26]

    Near-optimal regret for adversarial

    Jin, Tiancheng and Lancewicki, Tal and Luo, Haipeng and Mansour, Yishay and Rosenberg, Aviv , publisher =. Near-optimal regret for adversarial. Advances in Neural Information Processing Systems , volume=

  19. [27]

    Delay-Adapted Policy Optimization and Improved Regret for Adversarial

    Lancewicki, Tal and Rosenberg, Aviv and Sotnikov, Dmitry , booktitle =. Delay-Adapted Policy Optimization and Improved Regret for Adversarial. 2023 , volume =

    2023

  20. [28]

    Finite-Time Analysis of the Multiarmed Bandit Problem , year =

    Auer, Peter and Cesa-Bianchi, Nicol\`. Finite-Time Analysis of the Multiarmed Bandit Problem , year =. Machine Learning , pages =

  21. [29]

    Journal of Machine Learning Research , year =

    Thomas Jaksch and Ronald Ortner and Peter Auer , title =. Journal of Machine Learning Research , year =

  22. [30]

    Proceedings of the 25th Annual Conference on Learning Theory , pages =

    The Best of Both Worlds: Stochastic and Adversarial Bandits , author =. Proceedings of the 25th Annual Conference on Learning Theory , pages =. 2012 , volume =

    2012

  23. [31]

    Simultaneously Learning Stochastic and Adversarial Episodic

    Jin, Tiancheng and Luo, Haipeng , booktitle =. Simultaneously Learning Stochastic and Adversarial Episodic

  24. [32]

    The best of both worlds: stochastic and adversarial episodic

    Jin, Tiancheng and Huang, Longbo and Luo, Haipeng , booktitle =. The best of both worlds: stochastic and adversarial episodic

  25. [33]

    Proceedings of the 31st Conference On Learning Theory , pages =

    More Adaptive Algorithms for Adversarial Bandits , author =. Proceedings of the 31st Conference On Learning Theory , pages =. 2018 , volume =

    2018

  26. [34]

    Tsallis-

    Zimmert, Julian and Seldin, Yevgeny , journal=. Tsallis-

  27. [35]

    Improved Analysis of the

    Masoudian, Saeed and Seldin, Yevgeny , booktitle =. Improved Analysis of the. 2021 , volume =

    2021

  28. [36]

    Proceedings of the 36th International Conference on Machine Learning , pages =

    Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously , author =. Proceedings of the 36th International Conference on Machine Learning , pages =. 2019 , volume =

    2019

  29. [37]

    Proceedings of Thirty Fourth Conference on Learning Theory , pages =

    Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds , author =. Proceedings of Thirty Fourth Conference on Learning Theory , pages =. 2021 , volume =

    2021

  30. [38]

    Towards Best-of-All-Worlds Online Learning with Feedback Graphs , volume =

    Erez, Liad and Koren, Tomer , booktitle =. Towards Best-of-All-Worlds Online Learning with Feedback Graphs , volume =. 2021 , publisher =

    2021

  31. [39]

    Proceedings of The 27th Conference on Learning Theory , pages =

    A second-order bound with excess losses , author =. Proceedings of The 27th Conference on Learning Theory , pages =. 2014 , volume =

    2014

  32. [40]

    Proceedings of the 31st International Conference on Machine Learning , pages =

    One Practical Algorithm for Both Stochastic and Adversarial Bandits , author =. Proceedings of the 31st International Conference on Machine Learning , pages =. 2014 , volume =

    2014

  33. [41]

    29th Annual Conference on Learning Theory , pages =

    An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits , author =. 29th Annual Conference on Learning Theory , pages =. 2016 , volume =

    2016

  34. [42]

    An Improved Parametrization and Analysis of the

    Seldin, Yevgeny and Lugosi, Gábor , booktitle =. An Improved Parametrization and Analysis of the. 2017 , volume =

    2017

  35. [43]

    Adapting to Stochastic and Adversarial Losses in Episodic

    Ito, Shinji and Jamieson, Kevin and Luo, Haipeng and Maiti, Arnab and Tsuchiya, Taira , booktitle =. Adapting to Stochastic and Adversarial Losses in Episodic

  36. [44]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    A Blackbox Approach to Best of Both Worlds in Bandits and Beyond , author =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , volume =

    2023

  37. [45]

    Advances in Neural Information Processing Systems , volume=

    Taming heavy-tailed losses in adversarial bandits and the best-of-both-worlds setting , author=. Advances in Neural Information Processing Systems , volume=. 2024 , publisher =

    2024

  38. [46]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds , author =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , volume =

    2023

  39. [47]

    Proceedings of The 26th International Conference on Artificial Intelligence and Statistics , pages =

    Further Adaptive Best-of-Both-Worlds Algorithm for Combinatorial Semi-Bandits , author =. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics , pages =. 2023 , volume =

    2023

  40. [48]

    arXiv preprint arXiv:2504.07307 , year=

    Follow-the-perturbed-leader approaches best-of-both-worlds for the m-set semi-bandit problems , author=. arXiv preprint arXiv:2504.07307 , year=

  41. [49]

    International Conference on Artificial Intelligence and Statistics , pages=

    LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2025 , volume =

    2025

  42. [50]

    Proceedings of the 38th International Conference on Machine Learning , pages =

    Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously , author =. Proceedings of the 38th International Conference on Machine Learning , pages =. 2021 , volume =

    2021

  43. [51]

    Advances in Neural Information Processing Systems , volume=

    Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs , author=. Advances in Neural Information Processing Systems , volume=. 2022 , publisher =

    2022

  44. [52]

    Advances in Neural Information Processing Systems , volume=

    No-regret online reinforcement learning with adversarial losses and transitions , author=. Advances in Neural Information Processing Systems , volume=. 2023 , publisher =

    2023

  45. [53]

    International Conference on Algorithmic Learning Theory , pages=

    Hannan consistency in on-line learning in case of unbounded losses under partial monitoring , author=. International Conference on Algorithmic Learning Theory , pages=. 2006 , organization=

    2006

  46. [54]

    Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs , volume =

    Lee, Chung-Wei and Luo, Haipeng and Wei, Chen-Yu and Zhang, Mengxiao , booktitle =. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs , volume =

  47. [55]

    Journal of Machine Learning Research , year =

    Elad Hazan and Satyen Kale , title =. Journal of Machine Learning Research , year =

  48. [56]

    Proceedings of Algorithmic Learning Theory , pages =

    Sparsity, variance and curvature in multi-armed bandits , author =. Proceedings of Algorithmic Learning Theory , pages =. 2018 , volume =

    2018

  49. [57]

    Proceedings of the Thirty-Second Conference on Learning Theory , pages =

    Improved Path-length Regret Bounds for Bandits , author =. Proceedings of the Thirty-Second Conference on Learning Theory , pages =. 2019 , volume =

    2019

  50. [58]

    Proceedings of the 28th Conference on Learning Theory , pages =

    First-order regret bounds for combinatorial semi-bandits , author =. Proceedings of the 28th Conference on Learning Theory , pages =. 2015 , volume =

    2015

  51. [59]

    Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits:

    Jin, Tiancheng and Liu, Junyan and Luo, Haipeng , booktitle =. Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits:. 2023 , publisher =

    2023

  52. [60]

    Gap-Dependent Bounds for

    Zhong Zheng and Haochen Zhang and Lingzhou Xue , booktitle=. Gap-Dependent Bounds for

  53. [61]

    Proceedings of the 26th Annual Conference on Learning Theory , pages =

    Online Learning with Predictable Sequences , author =. Proceedings of the 26th Annual Conference on Learning Theory , pages =. 2013 , volume =

    2013

  54. [62]

    Proceedings of the 31st International Conference on Machine Learning , pages =

    Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm , author =. Proceedings of the 31st International Conference on Machine Learning , pages =. 2014 , volume =

    2014

  55. [63]

    SIAM Journal on Computing , year =

    Auer, Peter and Cesa-Bianchi, Nicoló and Freund, Yoav and Schapire, Robert E , title =. SIAM Journal on Computing , year =

  56. [64]

    Proceedings of Thirty Eighth Conference on Learning Theory , pages =

    Corrupted Learning Dynamics in Games , author =. Proceedings of Thirty Eighth Conference on Learning Theory , pages =. 2025 , volume =

    2025

  57. [65]

    Proceedings of the Nineteenth International Conference on Machine Learning , pages=

    Approximately optimal approximate reinforcement learning , author=. Proceedings of the Nineteenth International Conference on Machine Learning , pages=

  58. [66]

    Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics , pages =

    The adversarial stochastic shortest path problem with unknown transition probabilities , author =. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics , pages =. 2012 , volume =

    2012

  59. [67]

    , author=

    The Online Loop-free Stochastic Shortest-Path Problem. , author=. Proceedings of the 23rd Conference on Learning Theory , pages=

  60. [68]

    IEEE Transactions on Neural Networks , volume=

    Worst-case quadratic loss bounds for prediction using linear functions and gradient descent , author=. IEEE Transactions on Neural Networks , volume=. 1996 , publisher=

    1996

  61. [69]

    2003 , booktitle =

    Zinkevich, Martin , title =. 2003 , booktitle =

    2003

  62. [70]

    Information and Computation , volume=

    The weighted majority algorithm , author=. Information and Computation , volume=. 1994 , publisher=

    1994

  63. [71]

    arXiv preprint arXiv:1707.06347 , year=

    Proximal Policy Optimization Algorithms , author=. arXiv preprint arXiv:1707.06347 , year=

    arXiv

  64. [72]

    and Veness, Joel and Bellemare, Marc G

    Mnih, Volodymyr and Kavukcuoglu, Koray and Silver, David and Rusu, Andrei A. and Veness, Joel and Bellemare, Marc G. and Graves, Alex and Riedmiller, Martin and Fidjeland, Andreas K. and Ostrovski, Georg and Petersen, Stig and Beattie, Charles and Sadik, Amir and Antonoglou, I...

  65. [73]

    Nature Medicine , volume=

    The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care , author=. Nature Medicine , volume=

  66. [74]

    Empirical

    Maurer, Andreas and Pontil, Massimiliano , booktitle =. Empirical

  67. [75]

    Proceedings of the 25th Annual Conference on Learning Theory , pages =

    Online Optimization with Gradual Variations , author =. Proceedings of the 25th Annual Conference on Learning Theory , pages =. 2012 , volume =

    2012

  68. [76]

    Reinforcement Learning from Adversarial Preferences in Tabular

    Tsuchiya, Taira and Ito, Shinji and Luo, Haipeng , journal=. Reinforcement Learning from Adversarial Preferences in Tabular

  69. [77]

    Proceedings of Thirty Seventh Conference on Learning Theory , pages =

    Settling the sample complexity of online reinforcement learning , author =. Proceedings of Thirty Seventh Conference on Learning Theory , pages =. 2024 , volume =

    2024

  70. [78]

    M arkov Decision Processes with Arbitrary Reward Processes

    Yu, Jia Yuan and Mannor, Shie and Shimkin, Nahum. M arkov Decision Processes with Arbitrary Reward Processes. Recent Advances in Reinforcement Learning. 2008

    2008

  71. [79]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency , author =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , volume =

    2023

  72. [80]

    Proceedings of the 39th International Conference on Machine Learning , pages =

    First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach , author =. Proceedings of the 39th International Conference on Machine Learning , pages =. 2022 , volume =

    2022

  73. [81]

    2009 , author =

    Exploration–exploitation tradeoff using variance estimates in multi-armed bandits , journal =. 2009 , author =

    2009

  74. [82]

    Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds , volume =

    Tsuchiya, Taira and Ito, Shinji and Honda, Junya , booktitle =. Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds , volume =

  75. [83]

    Episodic Reinforcement Learning in Finite

    Domingues, Omar Darwiche and M. Episodic Reinforcement Learning in Finite. Proceedings of the 32nd International Conference on Algorithmic Learning Theory , pages =. 2021 , volume =

    2021

  76. [84]

    Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages =

    Contextual Bandit Algorithms with Supervised Learning Guarantees , author =. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , pages =. 2011 , volume =

    2011

  77. [85]

    International Conference on Machine Learning , year =

    Li, Mingyi and Tsuchiya, Taira and Yamanishi, Kenji , title =. International Conference on Machine Learning , year =

  78. [86]

    Narrowing the Gap between Adversarial and Stochastic

    Daniil Tiapkin and Evgenii Chzhen and Gilles Stoltz , booktitle=. Narrowing the Gap between Adversarial and Stochastic

  79. [87]

    Proceedings of the 32nd International Conference on Machine Learning , pages =

    Trust Region Policy Optimization , author =. Proceedings of the 32nd International Conference on Machine Learning , pages =. 2015 , volume =

    2015

  80. [88]

    Advances in Neural Information Processing Systems , publisher =

    Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning , author=. Advances in Neural Information Processing Systems , publisher =

  81. [89]

    Fine-Grained Gap-Dependent Bounds for Tabular

    Xu, Haike and Ma, Tengyu and Du, Simon , booktitle =. Fine-Grained Gap-Dependent Bounds for Tabular. 2021 , volume =

    2021

Pith tools

Reviewed July 1, 2026 · model on record in the stance chip above.