REVIEW 2 major objections 4 minor 1 cited by
Adaptive Sampling for Best Policy Identification in Markov Decision Processes
T0 review · 2 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read KLB-TS certifies the best policy of a discounted MDP with sample complexity at most 4U(φ) log(1/δ), where U is an explicit gap- and variance-dependent bound.
desk verdict Solid problem-specific framework for best-policy identification in MDPs, but the main theorem's constants appear to be off by a log-base error that undermines the stated PAC guarantee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the explicit near-optimal allocation ω(φ) of Corollary 1, which assigns sampling mass to each sub-optimal (s,a) proportionally to H_{sa} = 2/Δ_{sa}^2 + max(16 Var_{pφ(s,a)}[V*]/Δ_{sa}^2, 6 MD_{pφ(s,a)}[V*]^{4/3}/Δ_{sa}^{4/3}), and to each optimal action in state s proportionally to (1/S)√(H*(Σ H_{sa})), with H* = S(T3(φ)+T4(φ)). This allocation makes the upper bound U(φ)=2(H* + Σ_{s,a≠π*(s)} H_{sa}) explicit. Two mechanisms carry the algorithm: the C-tracking sampling rule forces the visit counts n_t(s,a)/t to converge to ω(φ) almost surely, and the KL-Ball stopping rule checks, through four KL-based test statistics ρ1,...,ρ4, that no alternative MDP can still be consistent with the samples; when the test passes, the empirical optimal policy must be the true one. The proof of the stopping rule rests on an event E that holds with probability 1−δ and implies φ∉Alt(φ̂_t).
What would settle it
Take a specific two-state MDP from the paper's non-convexity example in Figure 1 and compute T*(φ) by numerically solving the program (3) over a fine grid of allocations and alternative MDPs; if T*(φ) exceeds U(φ) from Corollary 1, the claimed upper bound is false. Alternatively, run KLB-TS on that MDP at δ=$10^{{-8}}$ over many seeds and check whether the average stopping time exceeds 4U(φ)log(1/δ) by more than a small constant fraction—the theorem allows the limsup to equal 4U(φ), so a persistent excess would falsify the asymptotic rate.
Extended reading notes
Core claim
For any discounted MDP with a unique optimal policy and a generative model, the paper establishes an explicit upper bound U(φ) on the characteristic time T*(φ) that governs the sample-complexity lower bound for any δ-correct algorithm. T*(φ) is defined by a non-convex program; U(φ) is obtained by allocating samples proportionally to the hardness of each sub-optimal state-action pair, roughly the inverse gap squared scaled by the variance or fourth-thirds deviation of the next-state value, and to the hardness of the optimal actions. The paper then proves that KLB-TS, which tracks this allocation with the C-tracking rule and stops with the KL-Ball rule, is δ-PAC and satisfies limsup_{δ→0} E[τδ]/log(1/δ) ≤ 4U(φ), with the same bound holding almost surely. It also proves the bound remains within the known minimax order O(SA/($Δmin^{2}$(1−γ)^3)) and beats the minimax rate when the variance of next-state values under optimal actions is small.
Load-bearing premise
The load-bearing premise is Assumption 1: the true MDP has exactly one optimal policy, so every sub-optimal action has a strictly positive gap; if two policies tie for optimal, the gap is zero, U(φ) degenerates, and the sample-complexity guarantee collapses. The analysis also assumes a generative model that can sample any state-action pair at any time.
Editorial extensions
If this is right
- KLB-TS certifies the true optimal policy with error probability δ and, as δ→0, uses at most 4U(φ) log(1/δ) samples in expectation and almost surely.
- The explicit allocation makes the algorithm practical: each round requires only evaluating formula (14) on the current empirical MDP and calling any black-box MDP solver.
- For MDPs whose value-function variance under optimal actions is small, U(φ) is strictly smaller than the minimax rate, so KLB-TS beats uniform sampling.
- The KL-Ball stopping rule is the first stopping rule for exact best-policy identification in MDPs; previous rules target ε-optimal policies and need an oracle for the minimal gap.
- The guarantee remains within the minimax order O(SA/(Δmin^2(1−γ)^3)) in the worst case.
Reading between the lines
- The factor 4 in the guarantee likely comes from two applications of (A+B)^2≤2(A^2+B^2) in Lemma 11; a tighter analysis could lower the constant, so the algorithm may be closer to U(φ) than the theorem states.
- For MDPs where the non-convex lower-bound program has a solution much smaller than U(φ), a solver for (3) could outperform KLB-TS; how large this gap can be is not quantified in the paper.
- Under trajectory-based sampling, visit counts become coupled, so the allocation ω(φ) is not necessarily achievable; extending this approach to online RL would require adding navigation constraints to the lower-bound program.
- Replacing Δmin with a target accuracy ε in T3 and T4 and in the stopping rule would yield a problem-specific ε-optimal policy-identification algorithm with the same KL-Ball structure, which could be tested numerically.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies fixed-confidence best-policy identification in discounted finite MDPs with a generative model. It first derives a problem-specific lower bound on the sample complexity via a change-of-measure argument, characterizes the associated allocation problem, and shows that the resulting program is non-convex. To bypass this difficulty, the authors propose an explicit upper bound U(φ) on the characteristic time T*(φ), expressed in terms of sub-optimality gaps, variances, and maximum deviations of next-state value functions, together with an explicit near-optimal allocation. They then introduce KLB-TS, an algorithm that tracks this allocation with a C-tracking rule and stops with a KL-Ball rule, and claim a δ-PAC guarantee (Theorem 2) as well as asymptotic sample-complexity bounds almost surely and in expectation (Proposition 2 and Theorem 3), both of the form limsup ≤ 4U(φ) log(1/δ). Numerical experiments compare KLB-TS with BESPOKE.
Significance. If the results hold, this is a valuable contribution to problem-dependent sample-complexity analysis for best-policy identification in MDPs. The lower-bound framework, the explicit allocation avoiding repeated solution of the non-convex program, and the variance/gap-dependent upper bound are useful and go beyond the existing minimax analyses. The numerical comparison with BESPOKE is also informative. However, two proof-level issues—an apparent logarithm-base mismatch in the constants defining T4(φ) and a union-bound gap in the PAC proof—are load-bearing for the stated guarantees and must be repaired before the main claims can be accepted.
major comments (2)
- [§4.2, Eq. (13); Appendix E.2, Eq. (29)] The constants defining T4(φ) are inconsistent with the base of the logarithms used in the derivation. The paper's KL divergences, the threshold function x(δ,n,m), and Lemmas 8–9 all use natural logarithms. However, the lower bound in Eq. (29) of Appendix E.2, when inverted, gives coefficients 288 ln(2)^2 ≈ 138.5 and 24 ln(2) ≈ 16.6 for the first two terms of V1(φ), whereas Theorem 1 states 27 and 8. Numerically, 288 log10(2)^2 ≈ 26.1 and 24 log10(2) ≈ 7.2, so the stated constants appear to use base-10 logarithms in an otherwise natural-log framework. Since T4 enters H*, U(φ), the correctness property (17), the stopping rule (19), and hence both Theorem 2 and Theorem 3, this is not a cosmetic issue: if V1 is the active term in the minimum defining T4, the required evidence is understated by a factor of about 5.1, and the algorithm may stop before the collected information suffices. Unless the whole framework is consistently re-expressed in a single logarithm base (including Pinsker-type inequalities and Lemmas 6, 8, 9), the constants in Eq. (13) must be corrected to the natural-log values and all dependent results re-checked.
- [Appendix F.1, inequalities (46)–(47)] The PAC proof contains a union-bound gap in bounding the third and fourth concentration events. The events E3,t(s) and E4,t(s) are defined with the data-dependent action π̂_t(s) inside the threshold x(δ′, n_t(s,π̂_t(s)), ·), but Lemmas 8 and 9 apply to a fixed (state, action) pair. To control these events one must union-bound over the A actions, giving an extra factor A (or the events must be indexed by the action and intersected with the event that this action was chosen). As written, the proof bounds each of the four families by δ′ and obtains the total 4S^3Aδ′; with the necessary extra union bound the total becomes of order S^3A^2δ′, which exceeds δ for the stated choice δ′ = δ/(4S^3A). This affects the δ-PAC guarantee of Theorem 2. The fix is straightforward—either redefine E3,t and E4,t with an explicit action index and use the outer union over (s,a), or decrease δ′ by a polynomial factor in A and recompute the final count—but as it stands the proof is incomplete.
minor comments (4)
- [Appendix G.1, Eqs. (48)–(50)] The expressions √log(δ′) should read √log(1/δ′), since δ′ < 1 and log(δ′) is negative; as written the square root is taken of a negative number.
- [Related Work, Section 2] The reference list contains unresolved placeholder citations of the form '?, Gheshlaghi Azar et al. (2013), ?, ?, Li et al. (2020)'; these should be completed before publication.
- [Abstract and Corollary 1] The abstract calls U(φ) a 'tight' upper bound of T*(φ), but the paper proves only the inequality T*(φ) ≤ U(φ) and does not establish a matching lower bound for U relative to T*(φ); the wording should be qualified accordingly.
- [Appendix B and F.1] There are minor typographical issues: 'Additional Proprerties' in the Appendix B heading and 'Liptschitz' for 'Lipschitz'; in Lemma 10 the notation i ∈ [|0,4|] is nonstandard and should be clarified.
Circularity Check
No circularity: KLB-TS bounds and stopping rule are derived from external concentration/variance inequalities and a standard track-and-stop analysis.
full rationale
The paper's derivation chain is self-contained. The lower bound (Proposition 1) follows from Lemma 1 together with a data-processing inequality and the defining events of a δ-PAC algorithm; it does not use the algorithm's design. The upper bound U(φ) (Theorem 1 and Corollary 1) is derived analytically: the alternative-MDP constraint (5) is decomposed into four terms, each bounded by KL divergences via Pinsker's inequality, a Hellinger/Cauchy-Schwarz argument (Lemma 4), and the variance inequality of Gheshlaghi Azar et al. (external, Lemma 6); the resulting optimization over the simplex is then solved in closed form. The allocation ω is the minimizer of the derived bound, not a fitted parameter. The algorithm's sampling rule imports the C-tracking rule and its convergence from Garivier and Kaufmann (2016), and the stopping rule uses threshold functions from concentration inequalities of Jonsson et al. (2020) (Lemmas 8 and 9 in the paper); these are external, independent results. The PAC proof (Theorem 2) uses the fact that the correctness event (43) is the contrapositive of inequalities (24)-(26)-(29)-(28) established in the upper-bound proof, and then bounds error probabilities by δ' via those external concentration lemmas. The asymptotic sample-complexity proof (Proposition 2 and Theorem 3) combines the C-tracking convergence to the allocation ω with Lemma 11, a numerical inequality about U(φ); it does not assume what it proves. No self-citation is load-bearing, and no parameter is fitted to the claimed sample-complexity result. The log-base constant mismatch in T4 flagged by a reviewer is a correctness/validity concern about the size of U(φ), not a circularity: the bound is not by construction equal to its input, and the main proof chain remains non-circular.
Assumptions & free parameters
assumptions (4)
- domain assumption The MDP phi has a unique optimal policy (Assumption 1, Section 3.1).
- domain assumption The learner has a generative model and can sample any (s,a) pair independently (Section 3.2).
- standard math Concentration inequalities of Jonsson et al. (2020), Lemma 8 and 9, and the variance inequality of Gheshlaghi Azar et al. (2013), Lemma 6, are used without proof.
- standard math C-tracking convergence result of Garivier and Kaufmann (2016) applies to the MDP allocation (Section 5.1, proof of Proposition 2 and Theorem 3).
Cite this review
Pith. "Pith review of Adaptive Sampling for Best Policy Identification in Markov Decision Processes." pith.science (2026). https://pith.science/paper/4TQHYRGN
@misc{pith2026200913405,
author = {Pith},
title = {Pith review of: Adaptive Sampling for Best Policy Identification in Markov Decision Processes},
year = {2026},
howpublished = {\url{https://pith.science/paper/4TQHYRGN}},
note = {Machine review of arXiv:2009.13405}
}
read the original abstract
We investigate the problem of best-policy identification in discounted Markov Decision Processes (MDPs) when the learner has access to a generative model. The objective is to devise a learning algorithm returning the best policy as early as possible. We first derive a problem-specific lower bound of the sample complexity satisfied by any learning algorithm. This lower bound corresponds to an optimal sample allocation that solves a non-convex program, and hence, is hard to exploit in the design of efficient algorithms. We then provide a simple and tight upper bound of the sample complexity lower bound, whose corresponding nearly-optimal sample allocation becomes explicit. The upper bound depends on specific functionals of the MDP such as the sub-optimality gaps and the variance of the next-state value function, and thus really captures the hardness of the MDP. Finally, we devise KLB-TS (KL Ball Track-and-Stop), an algorithm tracking this nearly-optimal allocation, and provide asymptotic guarantees for its sample complexity (both almost surely and in expectation). The advantages of KLB-TS against state-of-the-art algorithms are discussed and illustrated numerically.
Figures
Forward citations
Cited by 1 Pith paper
-
Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
The MVP algorithm achieves a gap-dependent variance-aware regret bound using a new conditional total variance measure, and a matching lower bound shows this variance dependence is necessary.
Reference graph
Works this paper leans on
-
[1]
Agarwal, A., Kakade, S., and Yang, L. F. (2019). Model-based reinforcement learning with a generative model is minimax optimal
work page 2019
-
[2]
Chernoff, H. (1959). Sequential design of experiments. Ann. Math. Statist. , 30(3):755--770
work page 1959
-
[3]
Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Feldman, V., Rakhlin, A., and Shamir, O., editors, 29th Annual Conference on Learning Theory , volume 49 of Proceedings of Machine Learning Research , pages 998--1027, Columbia University, New York, New York, USA. PMLR
work page 2016
-
[4]
Garivier, A. and Kaufmann, E. (2019). Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models
work page 2019
-
[5]
Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. (2013). Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning , 91(3):325--349
work page 2013
-
[6]
Jonsson, A., Kaufmann, E., Ménard, P., Domingues, O. D., Leurent, E., and Valko, M. (2020). Planning in markov decision processes with gap-dependent sample complexity
work page 2020
-
[7]
Kakade, S. M. (2003). On the sample complexity of reinforcement learning . PhD thesis, University of London, England
work page 2003
-
[8]
Kaufmann, E., Capp \'e , O., and Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research , 17(1):1--42
2016
Show all 15 references
-
[9]
and Koolen, W
Kaufmann, E. and Koolen, W. M. (2018). Mixture martingales revisited with applications to sequential tests and confidence intervals. ArXiv , abs/1811.11419
2018 arXiv
-
[10]
and Singh, S
Kearns, M. and Singh, S. (1999). Finite-sample convergence rates for q-learning and indirect algorithms. Advances in Neural Information Processing , 11
1999
-
[11]
and Robbins, H
Lai, T. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics , 6(1):4--2
1985
-
[12]
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Breaking the sample size barrier in model-based reinforcement learning with a generative model
2020
-
[13]
Reiss, R.-D. (1989). Approximate Distributions of Order Statistics: With Applications to Nonparametric Statistics. , pages 98--99. 1st edition
1989
-
[14]
F., and Ye, Y
Sidford, A., Wang, M., Wu, X., Yang, L. F., and Ye, Y. (2018). Near-optimal time and sample complexities for solving discounted markov decision process with a generative model
2018
-
[15]
J., and Brunskill, E
Zanette, A., Kochenderfer, M. J., and Brunskill, E. (2019). Almost horizon-free structure-aware best policy identification with a generative model. In Wallach, H., Larochelle, H., Beygelzimer, A., d Alch\' e -Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Infor...
2019
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.