Pith. sign in

REVIEW 2 major objections 9 minor 125 references

Bellman operators unify reinforcement learning's algorithmic zoo

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · glm-5.2

2026-07-09 22:35 UTC pith:QT4HVCC5

load-bearing objection Solid mathematical survey of RL that delivers on its stated purpose; unification holds through the core chapters but thins out toward the applications. the 2 major comments →

arxiv 2607.06935 v1 pith:QT4HVCC5 submitted 2026-07-08 math.OC cs.LGstat.ML

Mathematical methods of reinforcement learning

Denis Belomestny , Alexander Gasnikov , Egor Gladin , Alexey Naumov , Artemy Rubtsov , Yuri Sapronov , Daniil Tiapkin , Nikita Yudin This is my paper
classification math.OC cs.LGstat.ML
keywords learningmathematicalmethodsoptimizationreinforcementapproximationconstrainedmdps
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This survey argues that the diverse algorithms of reinforcement learning—from tabular Q-learning to policy gradient methods to PPO and RLHF—can be organized under a small set of shared mathematical structures: contraction mappings and fixed-point theory for dynamic programming, stochastic approximation and martingale methods for sample-based learning, and convex duality and mirror descent for optimization. The central claim is that value iteration, Q-learning, temporal-difference learning, and policy gradient updates are not ad hoc recipes but instances of a common operator-theoretic and variational framework, and that this unification makes the finite-sample bounds and convergence rates of each method transparent. The paper traces a single analytical thread from the Bellman equations (where contraction mappings guarantee convergence of value and policy iteration) through stochastic approximation (where martingale concentration inequalities yield sample complexity bounds for Q-learning and TD learning) to modern policy optimization (where mirror descent and trust-region methods connect to entropy-regularized MDPs and their convex reformulations via occupancy measures). Along the way it covers the transition from tabular to continuous state spaces via function approximation, the role of optimism and posterior sampling in exploration, and the application of these tools to constrained MDPs and to language model alignment.

Core claim

The paper establishes that the Bellman operator—defined as the mapping that takes a value function and returns the best one-step lookahead—is the load-bearing object across nearly all of reinforcement learning. In the full-knowledge setting, its contraction property guarantees that value iteration and policy iteration converge geometrically to the optimal value function, and that the optimal policy is simply the greedy policy with respect to the fixed point. In the sample-based setting, replacing the Bellman operator with an unbiased empirical estimator converts the fixed-point iteration into a stochastic approximation scheme, and the convergence analysis reduces to controlling a martingale:

What carries the argument

Bellman contraction operators, stochastic approximation with martingale-difference noise, mirror descent on occupancy measures, concentration inequalities for Markovian data

Load-bearing premise

The survey assumes that the mathematical structures connecting tabular dynamic programming to modern deep RL and language model alignment are deep enough to sustain a genuinely unified treatment, rather than being surface-level analogies that break down when one examines the distinct analytical challenges of each setting.

What would settle it

The unification would be weakened if the operator-theoretic and variational lenses fail to produce comparable finite-sample bounds or convergence rates across the different algorithm families—for instance, if the mirror-descent interpretation of policy gradient methods does not yield the same sample complexity guarantees that stochastic approximation gives for Q-learning.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the unification holds, a practitioner who understands the contraction-mapping analysis of value iteration can transfer the same fixed-point and martingale machinery to analyze Q-learning, TD learning, and even policy gradient methods, reducing the conceptual overhead of the field.
  • The convex reformulation of entropy-regularized MDPs via occupancy measures means that regularized policy optimization problems admit global rather than local convergence guarantees under appropriate conditions.
  • The sample complexity lower bounds, derived from bandit-like hard instances embedded in MDPs, provide a shared yardstick: any algorithm claiming to beat the minimax rates must exploit structure beyond what the generic MDP formulation assumes.
  • The connection between mirror descent in policy space and trust-region methods like TRPO and PPO suggests that the practical stability of these methods can be understood through the geometry of the KL-divergence regularizer rather than through heuristic arguments.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the operator-theoretic lens truly unifies tabular and function-approximation regimes, one would expect that finite-sample bounds for deep RL could be derived by combining the Bellman operator's contraction with concentration inequalities for the function class used—though the survey notes that non-linear function approximation remains the least theoretically developed area.
  • The parallel between entropy-regularized MDPs and convex optimization over occupancy measures suggests that accelerated first-order methods from convex optimization could be ported to policy search, potentially yielding faster-converging policy gradient algorithms.
  • The survey's treatment of RLHF as a KL-regularized policy optimization problem implies that alignment of language models is, mathematically, a regularized control problem on a structured MDP, and that the stability properties of PPO in this setting should be analyzable through the same mirror-descent framework used for tabular MDPs.

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

2 major / 9 minor

Summary. This manuscript is a survey of the mathematical foundations of reinforcement learning, targeting researchers in probability, optimization, and statistics. It covers Markov decision processes and Bellman operators (Chapter 3), generative model settings including model-based and model-free approaches (Chapter 4), policy evaluation via temporal difference learning (Chapter 5), forward model / online RL settings including multi-armed bandits and episodic MDPs (Chapter 6), continuous state spaces (Chapter 7), policy gradient methods (Chapter 8), and NLP applications including RLHF (Chapter 9). The paper aims to unify these topics under common operator-theoretic and variational lenses, emphasizing finite-sample bounds and asymptotic results.

Significance. The survey provides a valuable mathematical entry point into RL that is well-suited to the stated audience. Its core strength lies in the operator-theoretic thread connecting Chapters 3–6: Bellman operators as contractions (§3.1), the LP/saddle-point variational formulations (§3.3, §4.2), the martingale-based convergence proof for Q-learning (§4.2, Lemma 2), and the unified sample-complexity table (Table 2) are all accurately presented and genuinely interconnected. The hard-instance constructions in §4.1 (Figures 1–3) effectively illustrate lower bounds across DMDP, AMDP, and HMDP settings. The treatment of optimism-based algorithms (UCRL, UCBVI) in §6.2 with explicit regret proofs, and the linear function approximation results (§7.4, Theorem 11), are solid. The extension to policy gradient methods and RLHF/DPO in Chapters 8–9, while less mathematically deep, broadens the survey's relevance to current practice.

major comments (2)
  1. The abstract promises coverage of 'off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs).' However, the actual treatment is disproportionately thin. Off-policy evaluation receives only a few remarks in §5.1 (Remark 8 and Eq. 5.2) and a brief mention in §4.2. CMDPs are mentioned only in the LP formulation of §3.3 (one paragraph) with no algorithmic or sample-complexity discussion. Since these are advertised as core topics, either the abstract should be revised to accurately reflect the scope, or additional material should be added. As it stands, a reader directed to this survey for off-policy or constrained RL would find insufficient material.
  2. The unification claim—stated in the Abstract and Introduction as a central contribution—genuinely holds for Chapters 3–6, where the Bellman operator, fixed-point theory, and variational formulations provide a coherent analytical framework. However, the thread weakens substantially in Chapters 7–9. Chapter 9 (NLP applications) is largely descriptive with minimal operator-theoretic content, and the transition from the rigorous treatment of policy mirror descent (§8, citing [93]) to the RLHF/DPO/GRPO discussion is abrupt. The paper would benefit from either (a) explicitly acknowledging where the unification framework breaks down and why, or (b) adding a brief connecting discussion at the start of Chapter 8 or 9 that maps the application-level methods back to the operator/variational framework. This is a structural issue affecting the paper's central claim, not merely a presentation gap.
minor comments (9)
  1. §3.1.1, Eq. (3.5): The identity PV^π = P_π Q^π is derived inline but the notation P (without subscript) for the state-transition operator and P_π for the state-action operator could be confused. A brief clarifying remark on the distinction would aid readability.
  2. §3.3: The LP formulations for DMDP (Eq. 3.18) and AMDP (Eq. 3.15–3.16) are presented in close succession with different variable conventions (V vs. μ). A sentence clarifying the primal-dual correspondence in each case would help.
  3. §4.1, Table 2: The unified view of sample complexity is a nice contribution, but the notation H_eff, N_eff, ε_eff is introduced informally. A brief formal definition or a reference to where these quantities are defined in each setting would make the table more self-contained.
  4. §4.2, Algorithm 4 (RunEpoch): The variable N_m appears in the text description but the algorithm header uses N. The subscript m in the prose refers to the epoch index but this is not made explicit in the algorithm pseudocode. Consistent notation would avoid confusion.
  5. §6.2.3, proof of Proposition 4: The step where the double summation is bounded by '6H^2 S √(AK log(...))' uses a regrouping argument analogous to the UCRL proof, but the intermediate step showing the transition from the per-episode sum to the per-state-action sum is omitted. Making this step explicit for the reader would strengthen the proof.
  6. §8: The discussion of GRPO and Dr.GRPO (Eqs. following the PPO clip objective) introduces several advantage estimators. The notation Â^{Dr.GRPO} and Â^{GRPO} differs only in the superscript, and the distinction between 'group-relative baseline' and 'group-relative policy optimization' is not immediately clear from the notation alone.
  7. §9: The multi-agent RL section (final paragraphs) lists many system names (GPTSwarm, MaAS, G-Designer, etc.) in rapid succession. This reads more like a catalog than a mathematical survey. Consider condensing or moving to an appendix.
  8. Bibliography: Several references have incomplete formatting (e.g., [39] lists 'arXiv–2601' without a full identifier; [2] and [107]–[122] are arXiv preprints from 2025–2026 that may not be final). Verify all entries for completeness and DOIs/arXiv identifiers.
  9. The paper would benefit from a concluding section summarizing open problems and current research frontiers, particularly given the breadth of topics covered. The current transition from §9 directly to Acknowledgements is abrupt.

Circularity Check

0 steps flagged

No circularity found: survey of established results with self-contained proofs

full rationale

This is a survey paper that organizes known mathematical results in reinforcement learning. The proofs presented (Bellman contraction in §3.1.1, Q-learning convergence via Lemma 2 in §4.2, UCBVI regret bounds in §6.2.3, sample complexity bounds in Table 2) are standard expositions of established results, each cited to its original source. No new claim is derived from inputs that would make it circular by construction. Self-citations exist (e.g., Tiapkin et al. [27, 75], Samsonov et al. [42–44, 46, 50]) but constitute a small fraction of the 122 references and are not load-bearing for the paper's central organizational claim. The unification claim is expository—connecting algorithms through Bellman operators, fixed-point theory, LP/saddle-point formulations, and stochastic approximation—rather than a mathematical derivation that could reduce to its own inputs. No fitted parameter is presented as a prediction, no uniqueness theorem is invoked to force a conclusion, and no ansatz is smuggled through self-citation. The mathematical content is internally consistent and matches the cited literature.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

As a survey, the paper introduces no new free parameters, axioms, or invented entities. All assumptions are standard domain assumptions from the RL literature.

axioms (5)
  • standard math Bellman operators are gamma-contractions in the l-infinity norm
    Invoked in §3.1 to establish existence and uniqueness of fixed points for value functions. Standard result from Puterman [1].
  • domain assumption Markov chain induced by behavior policy is uniformly ergodic
    Invoked in §4.2 and §5.1 to ensure mixing and convergence of asynchronous Q-learning and TD learning under Markovian noise.
  • domain assumption Rewards are bounded in [0,1]
    Invoked throughout §3-6 to normalize value functions and derive sample complexity bounds.
  • domain assumption Optimal Q-function is Lipschitz continuous (for continuous settings)
    Invoked in §7.2 and §7.3 to justify kernel-based and adaptive discretization approaches in continuous state-action spaces.
  • domain assumption MDP is linear with bounded features (for linear function approximation)
    Invoked in §7.4 (Definition 7) to establish that Q-functions are linear in the feature map, enabling LSVI-UCB.

pith-pipeline@v1.1.0-glm · 61628 in / 1869 out tokens · 303968 ms · 2026-07-09T22:35:59.992893+00:00 · methodology

0 comments
read the original abstract

Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates for value and policy iteration, and temporal-difference schemes. We then develop the optimization perspective: stochastic approximation and martingale methods, convex duality and the role of regularization linking mirror/proximal methods. Function approximation is treated through linear and non-linear settings, covering stabilization, error decomposition, and sample-complexity via concentration inequalities for dependent data and mixing processes. We further cover off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs). Throughout we unify algorithmic templates under common operator and variational lenses, highlighting both finite-sample bounds and asymptotic results. Our presentation is intended to provide a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning.

Figures

Figures reproduced from arXiv: 2607.06935 by Alexander Gasnikov, Alexey Naumov, Artemy Rubtsov, Daniil Tiapkin, Denis Belomestny, Egor Gladin, Nikita Yudin, Yuri Sapronov.

Figure 1
Figure 1. Figure 1: Hard instance for DMDP. for the aggregation of rewards over time. The correspondence between different models is summarized in [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Hard instance for AMDP. However, in a generative model one can simulate multiple steps of the Markov chain, wait￾ing long enough between samples to let the chain mix so that successive rewards are nearly independent. Because the chain mixes in tmix = Θ β −1  steps, one can thin the simulation, taking one reward every O (tmix) transitions, and obtain effectively independent observa￾tions whose average is µ… view at source ↗
Figure 3
Figure 3. Figure 3: Hard instance for HMDP. The work [23] shows the tightness of this bound. For episodic hard instance the intuition means errors do not propagate across episodes but the horizon H scales the value difference. Finding an ε-optimal policy thus requires H3 dependence: H from the accumulated reward gap of size ε H at each stage and H2 from the number of episodes needed to estimate the overall gap. 4.2 Model-free… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

125 extracted references · 125 canonical work pages · 21 internal anchors

  1. [1]

    Puterman.Markov Decision Processes: Discrete Stochastic Dynamic Pro- gramming

    Martin L. Puterman.Markov Decision Processes: Discrete Stochastic Dynamic Pro- gramming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779. pages 4, 7, 8, 13

    work page 1994

  2. [2]

    The Landscape of Agentic Reinforcement Learning for LLMs: A Survey

    Guibin Zhang, Hejia Geng, Xiaohang Yu, Zhenfei Yin, Zaibin Zhang, Zelin Tan, Heng Zhou, Zhongzhi Li, Xiangyuan Xue, Yijiang Li, et al. The landscape of agentic rein- forcement learning for llms: A survey.arXiv preprint arXiv:2509.02547, 2025. pages 5, 57

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  3. [3]

    MIT press, 2022

    Mykel J Kochenderfer, Tim A Wheeler, and Kyle H Wray.Algorithms for decision making. MIT press, 2022. pages 5

    work page 2022

  4. [4]

    Deep belief markov models for pomdp inference.Neural networks, page 108386, 2025

    Giacomo Arcieri, Konstantinos G Papakonstantinou, Daniel Straub, and Eleni Chatzi. Deep belief markov models for pomdp inference.Neural networks, page 108386, 2025. pages 5

    work page 2025

  5. [5]

    A markovian decision process.Journal of mathematics and me- chanics, 6(5):679–684, 1957

    Richard Bellman. A markovian decision process.Journal of mathematics and me- chanics, 6(5):679–684, 1957. pages 9, 14

    work page 1957

  6. [6]

    An upper bound on the loss from approximate optimal-value functions.Machine Learning, 16(3):227–233, 1994

    Satinder P Singh and Richard C Yee. An upper bound on the loss from approximate optimal-value functions.Machine Learning, 16(3):227–233, 1994. pages 9

    work page 1994

  7. [7]

    R. A. Howard.Dynamic Programming and Markov Processes. MIT Press, Cambridge, MA, 1960. pages 10, 14

    work page 1960

  8. [8]

    Improved and generalized upper bounds on the complexity of policy iteration.Advances in Neural Information Processing Systems, 26, 2013

    Bruno Scherrer. Improved and generalized upper bounds on the complexity of policy iteration.Advances in Neural Information Processing Systems, 26, 2013. pages 10

    work page 2013

  9. [9]

    Springer, 2018

    Yurii Nesterov et al.Lectures on convex optimization, volume 137. Springer, 2018. pages 12 58

    work page 2018

  10. [10]

    From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs

    Julien Grand-Clément. From convex optimization to mdps: A review of first-order, second-order and quasi-newton methods for mdps.arXiv preprint arXiv:2104.10677,

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    A method for solving the convex programming problem with con- vergence rate o (1/k2)

    Yurii Nesterov. A method for solving the convex programming problem with con- vergence rate o (1/k2). InDokl akad nauk Sssr, volume 269, page 543, 1983. pages 12

    work page 1983

  12. [12]

    Springer Science & Business Media, 2013

    Yurii Nesterov.Introductory lectures on convex optimization: A basic course, vol- ume 87. Springer Science & Business Media, 2013. pages 12

    work page 2013

  13. [13]

    Some methods of speeding up the convergence of iteration methods

    Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1–17, 1964. pages 12

    work page 1964

  14. [14]

    A first-order approach to accelerated value iteration.Operations Research, 71(2):517–535, 2023

    Vineet Goyal and Julien Grand-Clement. A first-order approach to accelerated value iteration.Operations Research, 71(2):517–535, 2023. pages 12

    work page 2023

  15. [15]

    Pid accelerated value iter- ation algorithm

    Amir-massoud Farahmand and Mohammad Ghavamzadeh. Pid accelerated value iter- ation algorithm. InInternational Conference on Machine Learning, pages 3143–3153. PMLR, 2021. pages 12

    work page 2021

  16. [16]

    A unified view of entropy-regularized Markov decision processes

    Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy- regularized markov decision processes.arXiv preprint arXiv:1705.07798, 2017. pages 13

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  17. [17]

    Generative adversarial imitation learning.Advances in neural information processing systems, 29, 2016

    Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning.Advances in neural information processing systems, 29, 2016. pages 13

    work page 2016

  18. [18]

    Variational policy gradient method for reinforcement learning with general utilities

    Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572–4583, 2020. pages 13

    work page 2020

  19. [19]

    Stochastic Optimization under Hidden Convexity

    Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden con- vexity.arXiv preprint arXiv:2401.00108, 2023. pages 13

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  20. [20]

    Model-based reinforcement learning with a generative model is minimax optimal

    Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. InConference on Learning Theory, pages 67–83. PMLR, 2020. pages 14

    work page 2020

  21. [21]

    Minimax pac bounds on the sample complexity of reinforcement learning with a generative model

    Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91:325–349, 2013. pages 15, 19

    work page 2013

  22. [22]

    Breaking the sample size barrier in model-based reinforcement learning with a generative model.Advances in neural information processing systems, 33:12861–12872, 2020

    Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model.Advances in neural information processing systems, 33:12861–12872, 2020. pages 15

    work page 2020

  23. [23]

    Near-optimal time and sample complexities for solving markov decision processes with a generative model.Advances in Neural Information Processing Systems, 31, 2018

    Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model.Advances in Neural Information Processing Systems, 31, 2018. pages 15, 19

    work page 2018

  24. [24]

    Reinforcement learning: Theory and algorithms.CS Dept., UW Seattle, Seattle, WA, USA, Tech

    Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms.CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32,

    work page

  25. [25]

    Optimal sample complexity for average reward markov decision processes

    Shengbo Wang, Jose Blanchet, and Peter Glynn. Optimal sample complexity for average reward markov decision processes. InInternational Conference on Learning Representations, volume 2024, pages 29843–29861, 2024. pages 15, 16

    work page 2024

  26. [26]

    Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction.Advances in neural information processing systems, 33:7031–7043, 2020

    Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction.Advances in neural information processing systems, 33:7031–7043, 2020. pages 16 59

    work page 2020

  27. [27]

    From dirichlet to rubin: Optimistic exploration in rl without bonuses

    Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Ménard. From dirichlet to rubin: Optimistic exploration in rl without bonuses. InInternational Conference on Machine Learning, pages 21380–21431. PMLR, 2022. pages 16, 45

    work page 2022

  28. [28]

    Pac bounds for discounted mdps

    Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. InInternational Conference on Algorithmic Learning Theory, pages 320–334. Springer, 2012. pages 16

    work page 2012

  29. [29]

    Assouad, fano, and le cam

    Bin Yu. Assouad, fano, and le cam. InFestschrift for Lucien Le Cam: research papers in probability and statistics, pages 423–435. Springer, 1997. pages 17

    work page 1997

  30. [30]

    Towards tight bounds on the sample complexity of average-reward mdps

    Yujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward mdps. InInternational Conference on Machine Learning, pages 5055–

    work page

  31. [31]

    pages 17, 18

    PMLR, 2021. pages 17, 18

    work page 2021

  32. [32]

    Freedman’s inequality for matrix martingales

    Joel Tropp. Freedman’s inequality for matrix martingales. 2011. pages 20

    work page 2011

  33. [33]

    Is q-learning minimax optimal? a tight sample complexity analysis.Operations Research, 72(1): 222–236, 2024

    Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? a tight sample complexity analysis.Operations Research, 72(1): 222–236, 2024. pages 23, 25

    work page 2024

  34. [34]

    Stochastic approximation with cone-contractive operators: Sharp $\ell_\infty$-bounds for $Q$-learning

    Martin J. Wainwright. Stochastic approximation with cone-contractive operators: Sharpℓ∞-bounds forq-learning.arXiv preprint, arXiv:1905.06265, 2019. Available at arXiv. pages 23

    work page internal anchor Pith review Pith/arXiv arXiv 1905

  35. [35]

    Finite-sample convergence rates for q-learning and indirect algorithms.Advances in neural information processing systems, 11, 1998

    Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms.Advances in neural information processing systems, 11, 1998. pages 23

    work page 1998

  36. [36]

    A statistical analysis of polyak-ruppert averaged q-learning

    Xiang Li, Wenhao Yang, Jiadong Liang, Zhihua Zhang, and Michael I Jordan. A statistical analysis of polyak-ruppert averaged q-learning. InInternational Conference on Artificial Intelligence and Statistics, pages 2207–2261. PMLR, 2023. pages 23

    work page 2023

  37. [37]

    Variance-reduced $Q$-learning is minimax optimal

    Martin J Wainwright. Variance-reducedq-learning is minimax optimal.arXiv preprint arXiv:1906.04697, 2019. pages 24, 41

    work page internal anchor Pith review Pith/arXiv arXiv 1906

  38. [38]

    Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time.Mathematics of Operations Research, 45 (2):517–546, 2020

    Mengdi Wang. Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time.Mathematics of Operations Research, 45 (2):517–546, 2020. pages 25

    work page 2020

  39. [39]

    Efficiently solving mdps with stochastic mirror descent

    Yujia Jin and Aaron Sidford. Efficiently solving mdps with stochastic mirror descent. InInternational Conference on Machine Learning, pages 4890–4900. PMLR, 2020. pages 25

    work page 2020

  40. [40]

    Solving matrix games with near-optimal matvec complexity.arXiv e-prints, pages arXiv–2601, 2026

    Ishani Karmarkar, Liam O’Carroll, and Aaron Sidford. Solving matrix games with near-optimal matvec complexity.arXiv e-prints, pages arXiv–2601, 2026. pages 25

    work page 2026

  41. [41]

    Minimumcostflows, mdps, andℓ1-regressioninnearlylinear time for dense instances

    Jan Van Den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, ZhaoSong, andDiWang. Minimumcostflows, mdps, andℓ1-regressioninnearlylinear time for dense instances. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 859–869, 2021. pages 26

    work page 2021

  42. [42]

    Efficient global planning in large mdps via stochas- tic primal-dual optimization

    Gergely Neu and Nneka Okolo. Efficient global planning in large mdps via stochas- tic primal-dual optimization. InInternational Conference on Algorithmic Learning Theory, pages 1101–1123. PMLR, 2023. pages 26

    work page 2023

  43. [43]

    Tight high probability bounds for linear stochastic approximation with fixed stepsize.Advances in Neural Information Processing Systems, 34:30063–30074,

    Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Kevin Scaman, and Hoi-To Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize.Advances in Neural Information Processing Systems, 34:30063–30074,

    work page

  44. [44]

    Statistical inferenceforlinearstochasticapproximationwithmarkoviannoise.Advances in Neural Information Processing Systems, 38:174565–174626, 2026

    Sergey Samsonov, Marina Sheshukova, Eric Moulines, and Alexey Naumov. Statistical inferenceforlinearstochasticapproximationwithmarkoviannoise.Advances in Neural Information Processing Systems, 38:174565–174626, 2026. pages 27 60

    work page 2026

  45. [45]

    Finite-time high-probability bounds for polyak–ruppert averaged iterates of linear stochastic ap- proximation.Mathematics of Operations Research, 50(2):935–964, 2025

    Alain Durmus, Eric Moulines, Alexey Naumov, and Sergey Samsonov. Finite-time high-probability bounds for polyak–ruppert averaged iterates of linear stochastic ap- proximation.Mathematics of Operations Research, 50(2):935–964, 2025. pages 27

    work page 2025

  46. [46]

    Learning to predict by the methods of temporal differences

    Richard S Sutton. Learning to predict by the methods of temporal differences. In Machine Learning, volume 3, pages 9–44. Springer, 1988. pages 28

    work page 1988

  47. [47]

    Improved high-probability bounds for the temporal difference learning algorithm via exponential stability

    Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, and Eric Moulines. Improved high-probability bounds for the temporal difference learning algorithm via exponential stability. InThe Thirty Seventh Annual Conference on Learning Theory, pages 4511–

    work page

  48. [48]

    pages 28

    PMLR, 2024. pages 28

    work page 2024

  49. [49]

    Residual algorithms: Reinforcement learning with function approx- imation

    Leemon Baird. Residual algorithms: Reinforcement learning with function approx- imation. InMachine learning proceedings 1995, pages 30–37. Elsevier, 1995. pages 28

    work page 1995

  50. [50]

    A convergento(n)temporal- difference algorithm for off-policy learning with linear function approximation.Ad- vances in neural information processing systems, 21, 2008

    Richard S Sutton, Hamid Maei, and Csaba Szepesvári. A convergento(n)temporal- difference algorithm for off-policy learning with linear function approximation.Ad- vances in neural information processing systems, 21, 2008. pages 28

    work page 2008

  51. [51]

    S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and E

    R. S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and E. Wiewiora. Fast gradient-descent methods for temporal- difference learning with linear function approximation. InInternational Conference on Machine Learning, pages 993–1000, 2009. pages 28

    work page 2009

  52. [52]

    Gaussian approximation for two-timescale linear stochastic approximation

    Bogdan Butyrin, Artemy Rubtsov, Alexey Naumov, Vladimir V Ulyanov, and Sergey Samsonov. Gaussian approximation for two-timescale linear stochastic approximation. InProceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 36627–36635, 2026. pages 28

    work page 2026

  53. [53]

    Some aspects of the sequential design of experiments.Bulletin of the American Mathematical Society, 58(5):527–535, 1952

    Herbert Robbins. Some aspects of the sequential design of experiments.Bulletin of the American Mathematical Society, 58(5):527–535, 1952. pages 29

    work page 1952

  54. [54]

    Introduction to multi-armed bandits.Foundations and Trends in Machine Learning, 12(1-2):1–286, 2019

    Aleksandrs Slivkins. Introduction to multi-armed bandits.Foundations and Trends in Machine Learning, 12(1-2):1–286, 2019. pages 29

    work page 2019

  55. [55]

    Regret analysis of stochastic and non- stochastic multi-armed bandit problems.Foundations and Trends in Machine Learn- ing, 5(1):1–122, 2012

    Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and non- stochastic multi-armed bandit problems.Foundations and Trends in Machine Learn- ing, 5(1):1–122, 2012. pages 29

    work page 2012

  56. [56]

    Asymptoticallyefficientadaptiveallocationrules

    TzeLeungLaiandHerbertRobbins. Asymptoticallyefficientadaptiveallocationrules. Advances in Applied Mathematics, 6(1):4–22, 1985. pages 31

    work page 1985

  57. [57]

    Finite-time analysis of the multi- armed bandit problem.Machine Learning, 47(2-3):235–256, 2002

    Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multi- armed bandit problem.Machine Learning, 47(2-3):235–256, 2002. pages 31

    work page 2002

  58. [58]

    Onthelikelihoodthatoneunknownprobabilityexceedsanother in view of the evidence of two samples.Biometrika, 25(3/4):285–294, 1933

    WilliamRThompson. Onthelikelihoodthatoneunknownprobabilityexceedsanother in view of the evidence of two samples.Biometrika, 25(3/4):285–294, 1933. pages 33

    work page 1933

  59. [59]

    A tutorial on thompson sampling.Foundations and Trends®in Machine Learning, 11(1):1–96,

    Daniel Russo, Benjamin Roy, Ali Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling.Foundations and Trends®in Machine Learning, 11(1):1–96,

    work page

  60. [60]

    Cambridge University Press,

    Tor Lattimore and Csaba Szepesvári.Bandit algorithms. Cambridge University Press,

    work page

  61. [61]

    An empirical evaluation of thompson sampling.Ad- vances in neural information processing systems, 24, 2011

    Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling.Ad- vances in neural information processing systems, 24, 2011. pages 33

    work page 2011

  62. [62]

    Further optimal regret bounds for thompson sam- pling

    Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sam- pling. InArtificial Intelligence and Statistics, pages 99–107. PMLR, 2017. pages 33

    work page 2017

  63. [63]

    Analysis of thompson sampling for the multi-armed bandit problem

    Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. InConference on Learning Theory, pages 39–1, 2012. pages 33 61

    work page 2012

  64. [64]

    Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

    Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper con- fidence bounds for bandit problems.arXiv preprint arXiv:1204.5721, 2012. pages 34

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  65. [65]

    Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited

    Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578–598. PMLR, 2021. pages 36

    work page 2021

  66. [66]

    Near-optimal regret bounds for reinforcement learning.Journal of Machine Learning Research, 11:1563–1600, 2010

    Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning.Journal of Machine Learning Research, 11:1563–1600, 2010. pages 36

    work page 2010

  67. [67]

    A unifying view of optimism in episodic reinforce- ment learning

    Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforce- ment learning. InAdvances in Neural Information Processing Systems (NeurIPS), volume 33. Curran Associates, Inc., December 2020. Poster and conference paper. pages 37, 38

    work page 2020

  68. [68]

    Minimax regret bounds for reinforcement learning

    Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. InInternational conference on machine learning, pages 263–272. PMLR, 2017. pages 39

    work page 2017

  69. [69]

    Rusu, Joel Veness, Marc G

    Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human- level control through deep reinforcement ...

    work page 2015

  70. [70]

    Asynchronous methods for deep reinforcement learning

    Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. InProceedings of the 33rd International Conference on Machine Learning, pages 1928–1937. PMLR, 2016. pages 41

    work page 1928

  71. [71]

    Trust region policy optimization

    John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. InProceedings of the 32nd International Conference on Machine Learning, pages 1889–1897. PMLR, 2015. pages 41

    work page 2015

  72. [72]

    Generalization and exploration via randomized value functions

    Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. InInternational Conference on Machine Learning, pages 2377–2386. PMLR, 2016. pages 41, 45, 52

    work page 2016

  73. [73]

    Is q-learning provably efficient?Advances in neural information processing systems, 31, 2018

    Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient?Advances in neural information processing systems, 31, 2018. pages 42

    work page 2018

  74. [74]

    Almost optimal model-free reinforce- ment learningvia reference-advantage decomposition.Advances in Neural Information Processing Systems, 33:15198–15207, 2020

    Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforce- ment learningvia reference-advantage decomposition.Advances in Neural Information Processing Systems, 33:15198–15207, 2020. pages 42

    work page 2020

  75. [75]

    (more) efficient reinforcement learning via posterior sampling.Advances in Neural Information Processing Systems, 26, 2013

    Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling.Advances in Neural Information Processing Systems, 26, 2013. pages 43, 45

    work page 2013

  76. [76]

    Optimistic posterior sampling for reinforcement learn- ing: Worst-caseregretbounds

    Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learn- ing: Worst-caseregretbounds. InAdvances in Neural Information Processing Systems, volume 30 ofNeurIPS, 2017. Spotlight paper. pages 45

    work page 2017

  77. [77]

    Optimistic pos- terior sampling for reinforcement learning with few samples and tight guarantees

    Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Rémi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic pos- terior sampling for reinforcement learning with few samples and tight guarantees. In Advances in Neural Information Processing Systems, volume 35, 2022. pages 45 62

    work page 2022

  78. [78]

    Deep exploration via randomized value functions.Journal of machine learning research, 20(124):1–62,

    Ian Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen. Deep exploration via randomized value functions.Journal of machine learning research, 20(124):1–62,

    work page

  79. [79]

    Worst-case regret bounds for exploration via randomized value func- tions.Advances in neural information processing systems, 32, 2019

    Daniel Russo. Worst-case regret bounds for exploration via randomized value func- tions.Advances in neural information processing systems, 32, 2019. pages 45, 46

    work page 2019

  80. [80]

    Improved worst-case regret bounds for randomized least-squares value iteration

    Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized least-squares value iteration. InProceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6566–6573, 2021. pages 45, 46

    work page 2021

Showing first 80 references.