$\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

Jian Peng; Kefan Dong; Yining Wang; Yuan Zhou

REVIEW 2 major objections 5 minor 48 references

$\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A new algorithm, Adaptive Value-function Elimination, achieves the first √n cumulative regret bound for stochastic MDPs with general value function approximation under realizability and low Bellman rank.

desk verdict First sqrt(n)-regret for low Bellman rank MDPs, with a load-bearing closedness assumption that deserves scrutiny. read the letter →

arxiv 1909.02506 v3 pith:7L5EQJYR submitted 2019-09-05 cs.LG stat.ML

Kefan Dong , Jian Peng , Yining Wang , Yuan Zhou This is my paper · ORCID

classification cs.LGstat.ML MSC 68Q3290C40

keywords reinforcementlearningregretminimizationMarkovdecisionprocessesBellmanrankfunctionapproximationpolicyeliminationcontextualbanditsonline

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 claims that an agent can explore a Markov decision process whose state space is too large to enumerate, using a function class that contains the optimal Q-function, and still pay only square-root cumulative regret. The setting assumes a low Bellman rank: every Bellman error E(f,π_g,h) factorizes as an inner product of two vectors in R^M. The proposed algorithm, Adaptive Value-function Elimination (AVE), repeatedly eliminates hypotheses with large Bellman error, and the key move is to run each elimination step as a contextual bandit problem so that exploration costs little regret. If correct, this is the first √n-regret guarantee for stochastic MDPs with general value function approximation under realizability and low Bellman rank.

What carries the argument

The central object is the Bellman error functional E(f,π_g,h), and the central identity is the policy loss decomposition f(x1,π_f(x1)) − $V^{{π_f}}$(x1) = Σ_{h=1}^H E(f,π_f,h), which converts value suboptimality into accumulated Bellman error. The low-Bellman-rank assumption factorizes E(f,π_g,h) = ⟨ν_h(g), ξ_h(f)⟩ with values in R^M, so each elimination step can be viewed as cutting a slab through the set of vectors ξ_h(f); a volumetric argument adapted from OLIVE shows each such cut shrinks the minimum covering ellipsoid's volume by at least a constant factor, bounding the total number of eliminations by a polynomial in M and H. To avoid the regret cost of random exploration, AVE solves the elimination step as a contextual bandit: it finds a distribution P_k over hypotheses with low-variance importance-sampling weights, runs policies sampled from it, and uses active elimination with a doubling trick to discard poor hypotheses before measuring Bellman errors.

What would settle it

Construct a finite stochastic MDP with realizability and low Bellman rank that satisfies the deterministic-initial-state assumption but violates closedness under concatenation, using for example a shared-representation function class; run AVE and observe either that the optimal function is eliminated or that cumulative regret grows linearly with n.

Watch

Extended reading notes

Core claim

Under realizability (Assumption 1.1) and low Bellman rank (Assumption 1.2), plus two mild conditions—known deterministic initial state and closedness under layer-wise concatenation—AVE runs n trajectories with policies that improve over time, and with probability at least 1−1/(nH) its expected regret is O~(√($M^{2}$ A $H^{4}$ n $log^{3}$ |F|)), where M is the Bellman rank, A the number of actions, H the horizon, and F the hypothesis class. The proof hinges on the policy-loss decomposition f(x1,π_f(x1)) − $V^{{π_f}}$(x1) = Σ_{h=1}^H E(f,π_f,h): a hypothesis's value error equals its accumulated Bellman error, so eliminating hypotheses with large Bellman error is the right way to control regret. AVE replaces OLIVE's random-action roll-ins with low-variance sampling distributions borrowed from contextual bandit algorithms; active elimination and expert weighting ensure the policies actually executed are near-optimal while information about all remaining hypotheses is collected. A volumetric argument shows each elimination shrinks the covering ellipsoid of the Bellman-error vectors by a constant factor, so only polynomially many elimination phases occur in M and H.

Load-bearing premise

For the proof to go through, the function class must be closed under concatenation: any function assembled by taking one hypothesis per layer must itself lie in F; when this fails, the recursively constructed roll-in policies can fall outside the class and the elimination analysis no longer applies.

Editorial extensions

If this is right

An averaging over AVE's n policies yields a PAC guarantee, so √n regret and sample-efficient batch learning come from the same run.
The regret bound is polynomial in M, A, H and log|F| but does not depend directly on the state-space size, so exponential or infinite state spaces are tractable when function approximation is good.
A naive explore-first-then-exploit strategy built from the OLIVE PAC guarantee only achieves ~O(n^{2/3}) regret; AVE's √n rate shows elimination can be interleaved with exploration without losing.
The same algorithm extends to infinite hypothesis classes: if the policy class has Natarajan dimension d_Π and the value class has pseudo-dimension d_V, regret is O~(√(M^2 A H^4 n(d_Π + d_V))), replacing log|F| with the statistical dimension.
The doubling trick over error levels means policies with large Bellman error are never run for many trajectories, which is why the cumulative gap stays √n rather than linear.

Reading between the lines

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

The same contextual-bandit elimination recipe could plausibly convert other PAC elimination algorithms into √n-regret learners, provided a factorization analogous to Bellman rank holds.
The result suggests exploration difficulty in reinforcement learning is governed by the Bellman rank rather than the ambient state dimension, so problem classes with small M should be empirically much easier than tabular worst cases.
Closedness under concatenation is a real restriction in practice: neural networks with shared feature layers do not generally contain every layer-wise splice; testing whether AVE-style elimination fails on such classes, or relaxing the assumption via a wider class, is a direct next step.
A Bernstein-style concentration bound is what removes one factor of A in the infinite-hypothesis analysis, hinting that similar variance-aware arguments could sharpen other elimination-based RL guarantees.

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.

Desk Editor's Note

read the letter

You should know this paper delivers the first sqrt(n)-regret guarantee for stochastic MDPs with general value function approximation under realizability and low Bellman rank. That is real. The reduction of policy elimination to contextual bandits, replacing OLIVE's random-action exploration, is a genuine technical step, and the appendices give a detailed proof with explicit sample sizes. The result does not rest on curve-fitting; it is an upper bound proved from stated assumptions.

The soft spot is Assumption 2.2 (closedness under concatenation). The proof of Lemma 5.6 in Appendix C needs concatenated functions like g' ∘_{h'} f to remain in F, and the paper calls the assumption "very mild" without much support. It is not mild for natural function classes. A linear class with a shared parameter vector across layers violates the assumption, and enlarging F to its layer-wise closure can increase the Bellman rank. So the advertised dependence on M is actually the rank of the closed class, not necessarily of the original F. The abstract's "realizability and low Bellman rank" is therefore an overstatement; the honest statement is "realizability, low Bellman rank, and closedness under concatenation." The paper does list Assumption 2.2 explicitly, so the result is still sound within its scope. But the claim that the assumption is benign should have been argued or at least discussed with examples.

Other issues are minor: uninstantiated universal constants, some typos, and the usual reviewer burden of checking a long recursive argument without machine assistance. I did not find circular reasoning or a hidden fitting step. The citation pattern is appropriate, building on OLIVE and Dudik et al., and the related work section is accurate.

Who gets value from this: RL theorists working on function approximation and exploration. It is a significant step that fills a known gap between PAC guarantees and online regret for structured MDPs. It is not a practitioner's paper.

My recommendation: send it to peer review. It deserves a serious referee despite the Assumption 2.2 concern, and the authors should be asked to clarify the scope of that assumption and either weaken it or justify its mildness. The central argument is sound under the stated conditions.

Referee Report

2 major / 5 minor

Summary. The paper proposes Adaptive Value-function Elimination (AVE), an online reinforcement learning algorithm for finite-horizon stochastic MDPs with large state spaces and function approximation. Under realizability (Assumption 1.1) and a low Bellman rank condition (Assumption 1.2), the algorithm maintains an active hypothesis class, selects policies by optimism, estimates Bellman errors adaptively, and eliminates hypotheses using contextual-bandit-style importance weighting. The main result, Theorem 5.9 and Corollary 5.10, states that with high probability the cumulative regret over n trajectories is O~(sqrt(M^2 A H^4 n log^3 |F|)), where M is the Bellman rank, A is the number of actions, H is the horizon, and F is the hypothesis class. The paper also extends the result to infinite hypothesis classes using Natarajan and pseudo dimensions. The proof is detailed and largely self-contained, with concentration arguments and a volumetric elimination analysis in the appendices.

Significance. If the theorem holds as stated, this is a significant contribution: it would give the first square-root-regret bound for general value function approximation in stochastic MDPs under realizability and low Bellman rank, improving on the PAC-style guarantees of OLIVE and on black-box online-to-batch conversions. The paper's technical core is credible: the reduction of each elimination step to a contextual bandit problem is a genuinely useful idea, and the appended concentration and volumetric arguments are careful and specific. The claimed dependence on the Bellman rank M and on log |F| is attractive. However, the advertised scope is broader than what is actually proved: the regret bound is conditional on Assumption 2.2 (closedness under layer-wise concatenation), which is load-bearing and materially restricts the function classes covered. The central theorem appears sound under that assumption, but the paper must clearly state the assumption in its main theorem and temper the abstract's claim that the result holds under only realizability and low Bellman rank.

major comments (2)

[Assumption 2.2, Appendix C (proof of Lemma 5.6), Algorithm 2 Line 3] Assumption 2.2 is load-bearing for the proof of Lemma 5.6 and hence for the main regret bound. In Appendix C, the volumetric argument needs the identity |E(f, π_g, h)| = |E(g, π_g, h)| for g = g' ∘_{h'} f. The first equality follows from agreement of g and f from layer h' onward, but the second uses Assumption 1.2, which applies only when both functions lie in F. The text explicitly invokes Assumption 2.2 to conclude g ∈ F. Without this assumption, the concatenated function g may be outside F, so neither E(f, π_g, h) nor E(g, π_g, h) is covered by the Bellman factorization. The same issue arises at Algorithm 2, Line 3, where Check is called on the distribution {(g ∘_h f, P_k(f))}_{f ∈ G}; these concatenated objects are not known to be hypotheses in F. Thus Theorem 5.9 and Corollary 5.10 are proved only for function classes closed under layer-wise concatenation, and the abstract's claim of a sqrt(n)-regret result under 'realizability and low Bellman ranks' overstates the scope.
[Section 2.3, Assumption 2.2] The claim that Assumption 2.2 is 'very mild' is not supported, and enlarging the function class to force closure is not a harmless normalization. For example, a natural linear class F = {f_θ(x_h, a) = θ^T φ_h(x_h, a) with a single parameter vector θ shared across layers} satisfies realizability and low Bellman rank in many settings, but the layer-wise concatenation of two hypotheses with different θ_h is generally not in F. The argument that independent per-layer approximation is 'almost always used' is a statement about practice, not a mathematical guarantee, and it does not cover shared-representation models. Moreover, the Bellman rank M of the closure of F can be larger than the rank of F, so the advertised dependence on M is on the rank of the enlarged class. The paper should either prove that closure preserves low Bellman rank up to a bounded factor, or explicitly state separately that the regret bound holds for a class satisfying Assumption 2.2 and indicate how restrictive this is.

minor comments (5)

[Algorithm 2, Line 7] The label 'pesudo-learn' should be 'pseudo-learn'.
[Section 5.3, proof of Lemma 5.3] In the display after Eq. (37), the term '(12 + 4)ǫ_k' should presumably be '(12H + 4)ǫ_k', consistent with the surrounding inequalities.
[Definition 6.2 and surrounding text] The phrase 'Pesudo dimension' appears both in the main text and in Definition 6.2; it should be 'pseudo dimension'.
[Theorem 5.9 and Corollary 5.10] The theorem statements should explicitly list Assumptions 1.1, 1.2, 2.1, and 2.2 rather than leaving them implicit from Section 2, because Assumption 2.2 is not a standard part of the low-Bellman-rank framework and is used essentially in the proof.
[Appendix B] The constants c_1 through c_4 (and c_5 through c_7 in Appendix E) are only specified as 'large enough universal constants'; giving explicit values or a table of dependencies would make the sample-size choices easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the regret bound is a conditional upper-bound theorem proved from explicit assumptions and external prior results.

full rationale

The paper's derivation is a conditional upper-bound proof, not a fitted prediction. The algorithm AVE is analyzed under explicitly stated assumptions: realizability (Assumption 1.1), low Bellman rank (Assumption 1.2), deterministic initial state (Assumption 2.1), and closedness under concatenation (Assumption 2.2). The main theorem (Theorem 5.9) is derived from these assumptions using concentration lemmas, a doubling trick, the volumetric argument adapted from Jiang et al. [1], and contextual-bandit estimation techniques from Dudik et al. [2]. The cited foundational results are external prior publications with no author overlap with the present paper, and they are not invoked as a substitute for the proof. The preservation of f* is shown from the Bellman equation and realizability, i.e., E(f*, pi, h) = 0, not from the regret claim itself. Corollary 5.10 is obtained by optimizing the epsilon parameter in Theorem 5.9, not by renaming a fitted quantity as a prediction. Assumption 2.2 is load-bearing in Lemma 5.6 because it places recursively concatenated hypotheses back in F, but it is an explicit assumption rather than a conclusion derived from the target result; whether it is 'very mild' is a scope and correctness concern, not circularity. No equation in the paper reduces by construction to its own inputs, and no fitted parameter is presented as a prediction. Accordingly, the circularity score is 0.

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

The central claim depends on Assumptions 1.1, 1.2, 2.1, and 2.2, plus bounded rewards and a finite or bounded-complexity function class. No free parameters are fitted to data; the universal constants in the proof are existence-level. The most fragile input is Assumption 2.2, which is structurally necessary for the recursive elimination analysis.

assumptions (6)

domain assumption Assumption 1.1 (Realizability): there exists f* in F such that Q^{pi*}_h = f* for all h.
Core structural assumption guaranteeing the optimal policy is representable; used to show f* is never eliminated in Lemma 5.3(c).
domain assumption Assumption 1.2 (Low Bellman rank): E(f, pi_g, h) = <nu_h(g), xi_h(f)> with ||nu_h(g)|| ||xi_h(f)|| <= zeta for all f, g, h.
Provides the factorization used by the volumetric argument to bound the number of elimination steps by poly(M, H).
domain assumption Assumption 2.1: the initial state x1 is deterministic and known.
The paper argues it is without loss of generality by adding a dummy first layer.
domain assumption Assumption 2.2: F is closed under per-layer concatenation of its restrictions.
Load-bearing: Appendix C uses it to keep recursively constructed roll-in functions in F so Bellman factorization applies. It may fail for shared-representation function classes and is called very mild without a supporting argument.
domain assumption Bounded rewards and value functions in [0,1] are used throughout, for example in Lemma 5.4 and the Hoeffding and Freedman inequalities.
Needed for the concentration estimates in Appendix B; not stated as a numbered assumption in the abstract.
standard math Finite hypothesis class F for Theorem 5.9; Section 6 extends to infinite classes with Natarajan and pseudo-dimension bounds.
Finite |F| appears in log|F| terms and union bounds; the extension replaces it with statistical complexity dimensions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank." pith.science (2026). https://pith.science/paper/7L5EQJYR

@misc{pith2026190902506,
  author       = {Pith},
  title        = {Pith review of: $\sqrtn$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7L5EQJYR}},
  note         = {Machine review of arXiv:1909.02506}
}

abstract

In this paper, we consider the problem of online learning of Markov decision processes (MDPs) with very large state spaces. Under the assumptions of realizable function approximation and low Bellman ranks, we develop an online learning algorithm that learns the optimal value function while at the same time achieving very low cumulative regret during the learning process. Our learning algorithm, Adaptive Value-function Elimination (AVE), is inspired by the policy elimination algorithm proposed in (Jiang et al., 2017), known as OLIVE. One of our key technical contributions in AVE is to formulate the elimination steps in OLIVE as contextual bandit problems. This technique enables us to apply the active elimination and expert weighting methods from (Dudik et al., 2011), instead of the random action exploration scheme used in the original OLIVE algorithm, for more efficient exploration and better control of the regret incurred in each policy elimination step. To the best of our knowledge, this is the first $\sqrt{n}$-regret result for reinforcement learning in stochastic MDPs with general value function approximation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 46 canonical work pages

[1]

Schapire

Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langfor d, and Robert E. Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In Proceedings of the International Conference on Machine Learning (ICML) , pages 1704–1713, 2017. 1, 3, 4, 5, 6, 8, 13, 14, 21, 22, 29, 30, 34

work page 2017
[2]

Eﬃcient optimal learning for contextual bandits

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, Jo hn Langford, Lev Reyzin, and Tong Zhang. Eﬃcient optimal learning for contextual bandits. In Proceedings of the Conference on Uncertainty in Artiﬁcial Intelligence (UAI) , pages 169–178, 2011. 1, 6, 7, 8, 26, 28

work page 2011
[3]

Dynamic programming and optimal control , volume 1

Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, a nd Dimitri P Bertsekas. Dynamic programming and optimal control , volume 1. Athena scientiﬁc Belmont, MA, 1995. 2

work page 1995
[4]

Approximate Dynamic Programming: Solving the curses of dim ensionality, volume

Warren B Powell. Approximate Dynamic Programming: Solving the curses of dim ensionality, volume

work page
[5]

Human-level control through deep reinforcement learning

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovsk i, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015. 2

work page 2015
[6]

Unifying count-based exploration and intrinsic motivation

Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Proceedings of Advances in Neural Infor- mation Processing Systems (NIPS) , pages 1471–1479, 2016. 2

work page 2016
[7]

Mastering the game of go with deep neural networks and tree search

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, M arc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016. 2

work page 2016
[8]

Ma stering the game of go without human knowledge

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Anton oglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Ma stering the game of go without human knowledge. Nature, 550(7676):354, 2017. 2

work page 2017

Show all 48 references

[9]

Deep reinforcement learning for robotic manipulation with asynchronous oﬀ-policy updates

Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous oﬀ-policy updates. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) , pages 3389–3396, 2017. 2

2017
[10]

Is Q-learning provably eﬃcient? In Proceedings of Advances in Neural Information Processing S ystems (NeurIPS) , pages 4863–4873,

Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jor dan. Is Q-learning provably eﬃcient? In Proceedings of Advances in Neural Information Processing S ystems (NeurIPS) , pages 4863–4873,
[11]

Tighter problem-dependen t regret bounds in reinforcement learn- ing without domain knowledge using value function bounds

Andrea Zanette and Emma Brunskill. Tighter problem-dependen t regret bounds in reinforcement learn- ing without domain knowledge using value function bounds. arXiv preprint arXiv:1901.00210 , 2019. 2

1901 arXiv
[12]

Min imax regret bounds for reinforcement learning

Mohammad Gheshlaghi Azar, Ian Osband, and R´ emi Munos. Min imax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machin e Learning-Volume 70 , pages 263–272. JMLR. org, 2017. 2

2017
[13]

Pac model-free reinforcement learning

Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model-free reinforcement learning. In Proceedings of the 23rd international conference on Machin e learning , pages 881–888. ACM, 2006. 2

2006
[14]

Speedy q-learning

Mohammad Gheshlaghi Azar, Remi Munos, Mohammad Ghavamza deh, and Hilbert Kappen. Speedy q-learning. In Advances in neural information processing systems , 2011. 2

2011
[15]

Learning rates for q-lear ning

Eyal Even-Dar and Yishay Mansour. Learning rates for q-lear ning. Journal of Machine Learning Research, 5(Dec):1–25, 2003. 2

2003
[16]

Variance re duced value iteration and faster al- gorithms for solving markov decision processes

Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance re duced value iteration and faster al- gorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 770–787. Society for Industrial and A...
[17]

An analysis of bid-price con trols for network revenue manage- ment

Kalyan Talluri and Garrett Van Ryzin. An analysis of bid-price con trols for network revenue manage- ment. Management Science , 44(11-part-1):1577–1593, 1998. 2

1998
[18]

Dynamic bid prices in revenue management

Daniel Adelman. Dynamic bid prices in revenue management. Operations Research, 55(4):647–661,
[19]

Asynchronous metho ds for deep reinforcement learning

Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Gra ves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous metho ds for deep reinforcement learning. In Proceedings of the International Conference on Machine Lea rning (ICML) , pages 19...

1928
[20]

The malmo platform for arti- ﬁcial intelligence experimentation

Matthew Johnson, Katja Hofmann, Tim Hutton, and David Bigne ll. The malmo platform for arti- ﬁcial intelligence experimentation. In Proceedings of the International Joint Conference on Artiﬁ cial Intelligence (IJCAI) , pages 4246–4247, 2016. 3

2016
[21]

Gambling in a rigged casino: The adversarial multi-armed bandit problem

Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Sc hapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the IEEE Annual Conference on Foundations of Computer Science (FOCS) , pages 322–331. IEEE, 1995. 5

1995
[22]

Learning from delayed rewards

Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, King’s College, Cambridge, 1989. 7

1989
[23]

Q-learning

Christopher JCH Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3-4):279–292, 1992. 7

1992
[24]

Asynchronous stochastic approximation and q -learning

John N Tsitsiklis. Asynchronous stochastic approximation and q -learning. Machine Learning, 16(3):185– 202, 1994. 7

1994
[25]

Regu- larized policy iteration with nonparametric function spaces

Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Sz epesv´ ari, and Shie Mannor. Regu- larized policy iteration with nonparametric function spaces. Journal of Machine Learning Research , 17(1):4809–4874, 2016. 7

2016
[26]

Finite-sample analysis of least- squares policy iteration

Alessandro Lazaric, Mohammad Ghavamzadeh, and R´ emi Muno s. Finite-sample analysis of least- squares policy iteration. Journal of Machine Learning Research , 13(Oct):3041–3074, 2012. 7 23

2012
[27]

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

Andr´ as Antos, Csaba Szepesv´ ari, and R´ emi Munos. Learning near-optimal policies with bellman-residual minimization based ﬁtted policy iteration and a single sample path. Machine Learning, 71(1):89–129,
[28]

Finite-time bounds for ﬁt ted value iteration

R´ emi Munos and Csaba Szepesv´ ari. Finite-time bounds for ﬁt ted value iteration. Journal of Machine Learning Research, 9(May):815–857, 2008. 7

2008
[29]

Information-theoretic consideratio ns in batch reinforcement learning

Jinglin Chen and Nan Jiang. Information-theoretic consideratio ns in batch reinforcement learning. In Proceedings of the International Conference on Machine Lea rning (ICML) , pages 1042–1051, 2019. 7

2019
[30]

Stable function approximation in dynamic pro gramming

Geoﬀrey J Gordon. Stable function approximation in dynamic pro gramming. In Proceedings of the International Conference on Machine Learning (ICML) , pages 261–268. Elsevier, 1995. 7

1995
[31]

P rovably eﬃcient reinforcement learning with linear function approximation

Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. P rovably eﬃcient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388 , 2019. 7

1907 arXiv
[32]

On oracle-eﬃcient pac rl with rich observations

Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agar wal, John Langford, and Robert E Schapire. On oracle-eﬃcient pac rl with rich observations. In Proceedings of Advances in Neural Infor- mation Processing Systems (NeurIPS) , pages 1422–1432, 2018. 7

2018
[33]

Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, M iroslav Dudik, and John Langford

Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, M iroslav Dudik, and John Langford. Provably eﬃcient rl with rich observations via latent state decoding . In Proceedings of the International Conference on Machine Learning (ICML) , pages 1665–1674, 2019. 7

2019
[34]

Eﬃcient reinforcement learnin g in deterministic systems with value function generalization

Zheng Wen and Benjamin Van Roy. Eﬃcient reinforcement learnin g in deterministic systems with value function generalization. Mathematics of Operations Research , 42(3):762–782, 2017. 7

2017
[35]

N ear-optimal time and sample complexities for solving discounted markov decision process with a ge nerative model

Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. N ear-optimal time and sample complexities for solving discounted markov decision process with a ge nerative model. In Proceedings of Advances in Neural Information Processing Systems (NeurIP S), pages 5186–5196, 2018. 7

2018
[36]

Glo bal convergence of policy gradient methods for linearized control problems

Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi. Glo bal convergence of policy gradient methods for linearized control problems. In Proceedings of the International Conference on Machine Learning (ICML), pages 1467–1476, 2018. 7

2018
[37]

Stochastic approximation with cone-contr active operators: Sharp ℓ∞-bounds for q-learning

Martin J Wainwright. Stochastic approximation with cone-contr active operators: Sharp ℓ∞-bounds for q-learning. arXiv preprint arXiv:1905.06265 , 2019. 7

1905 arXiv
[38]

Taming the monster: A fast and simple algorithm for contextual bandits

Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of International Conference on Machine Learning (ICML) , pages 1638–1646, 2014. 7, 21, 26

2014
[39]

https://arxiv.org/abs/1905.10389

Yang Lin and Wang Mengdi. https://arxiv.org/abs/1905.10389. arXiv preprints arXiv:1905.10389 ,

1905 arXiv
[40]

On learning sets and functions

Balas K Natarajan. On learning sets and functions. Machine Learning, 4(1):67–97, 1989. 21

1989
[41]

Decision theoretic generalizations of the pac mo del for neural net and other learning applications

David Haussler. Decision theoretic generalizations of the pac mo del for neural net and other learning applications. Information and computation , 100(1):78–150, 1992. 21

1992
[42]

Rates of convergence in the central limit the orem for empirical processes

Pascal Massart. Rates of convergence in the central limit the orem for empirical processes. In Annales de l’IHP Probabilit´ es et statistiques, volume 22, pages 381–423, 1986. 21, 36

1986
[43]

On general minimax theorems

Maurice Sion et al. On general minimax theorems. Paciﬁc Journal of Mathematics , 8(1):171–176, 1958. 26

1958
[44]

On minimum volume ellipsoids containing part of a give n ellipsoid

Michael J Todd. On minimum volume ellipsoids containing part of a give n ellipsoid. Mathematics of Operations Research, 7(2):253–261, 1982. 30 24

1982
[45]

Sphere packing numbers for subsets of the bo olean n-cube with bounded vapnik- chervonenkis dimension

David Haussler. Sphere packing numbers for subsets of the bo olean n-cube with bounded vapnik- chervonenkis dimension. J. Comb. Theory, Ser. A , 69:217–232, 1995. 34

1995
[46]

Springer Science & Business Media, 2013

Luc Devroye, L´ aszl´ o Gy¨ orﬁ, and G´ abor Lugosi.A probabilistic theory of pattern recognition , volume 31. Springer Science & Business Media, 2013. 36

2013
[47]

Convergence of stochastic processes

David Pollard. Convergence of stochastic processes . Springer Science & Business Media, 2012. 36 25 A Low variance estimation Line 2 of Eliminate ﬁnds a distribution that achieves the low variance condition (i.e., Eq. ( 9)). In this section, we show that the distribution Pk ex...

2012
[703]

John Wiley & Sons, 2007. 2

2007

Pith tools

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

[1] [1]

Schapire

Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langfor d, and Robert E. Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In Proceedings of the International Conference on Machine Learning (ICML) , pages 1704–1713, 2017. 1, 3, 4, 5, 6, 8, 13, 14, 21, 22, 29, 30, 34

work page 2017

[2] [2]

Eﬃcient optimal learning for contextual bandits

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, Jo hn Langford, Lev Reyzin, and Tong Zhang. Eﬃcient optimal learning for contextual bandits. In Proceedings of the Conference on Uncertainty in Artiﬁcial Intelligence (UAI) , pages 169–178, 2011. 1, 6, 7, 8, 26, 28

work page 2011

[3] [3]

Dynamic programming and optimal control , volume 1

Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, a nd Dimitri P Bertsekas. Dynamic programming and optimal control , volume 1. Athena scientiﬁc Belmont, MA, 1995. 2

work page 1995

[4] [4]

Approximate Dynamic Programming: Solving the curses of dim ensionality, volume

Warren B Powell. Approximate Dynamic Programming: Solving the curses of dim ensionality, volume

work page

[5] [5]

Human-level control through deep reinforcement learning

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovsk i, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015. 2

work page 2015

[6] [6]

Unifying count-based exploration and intrinsic motivation

Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Proceedings of Advances in Neural Infor- mation Processing Systems (NIPS) , pages 1471–1479, 2016. 2

work page 2016

[7] [7]

Mastering the game of go with deep neural networks and tree search

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, M arc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016. 2

work page 2016

[8] [8]

Ma stering the game of go without human knowledge

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Anton oglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Ma stering the game of go without human knowledge. Nature, 550(7676):354, 2017. 2

work page 2017