Pith. sign in

REVIEW 3 major objections 5 minor 37 references

This paper proves the first non-asymptotic sample-complexity guarantees for the Navigate-and-Stop algorithm in online best policy identification, showing that after enough exploration its stopping time matches the asymptotic optimum up to s

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 · deepseek-v4-flash

2026-08-01 18:44 UTC pith:BH6LVX2N

load-bearing objection First non-asymptotic guarantee for NaS in online BPI, with a proof structure that mostly checks out, but Assumption 3 narrows the scope more than the abstract admits. the 3 major comments →

arxiv 2607.17201 v1 pith:BH6LVX2N submitted 2026-07-19 stat.ML cs.LG

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

Joseph Lazzaro , Alessio Russo , Aldo Pacchiano This is my paper
classification stat.ML cs.LG MSC 90C4062L05
keywords best policy identificationnon-asymptotic sample complexityNavigate-and-Stoponline reinforcement learningpure explorationMarkov decision processessharpnessfixed-confidence identification
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.

The paper asks how many interactions an agent needs to identify an optimal policy in an unknown MDP with confidence 1−δ. Previous work showed the Navigate-and-Stop (NaS) algorithm is asymptotically optimal as δ→0, but nothing was known for finite confidence. The paper closes that gap with the first non-asymptotic upper bounds for NaS: the expected stopping time is controlled by the characteristic time T(M) log(1/δ) plus explicit sublinear errors that depend on the MDP's connectivity, mixing time, and the sharpness of the allocation objective. Under a linear-sharpness condition, the bound becomes fully explicit with all correction exponents strictly below 1. This matters because finite-confidence behavior, not just the δ→0 limit, is what practitioners actually observe.

Core claim

The central claim is that, under Assumptions 1–3, the Navigate-and-Stop algorithm is δ-correct and its expected sample complexity satisfies E[τδ] ≤ inf{t : b(t,δ) < (t−√t)T(M)^{-1} − ℓ0(t,M)} + 7, where b(t,δ) is the log-threshold of the stopping rule and ℓ0 is a sublinear error term. When the characteristic-time objective T(ω;M)^{-1} is linearly sharp around its maximizers, the paper derives the explicit form E[τδ] ≤ Bδ + Õ(√Bδ + T(M) Σ_i A_i Bδ^{r_i}) with Bδ = T(M) log(1/δ) and all r_i < 1, so E[τδ] = T(M) log(1/δ) + o(log(1/δ)) as δ→0. The constants A_i expose how connectivity (m, η_m, κ_M), the stability of the feasible allocation set (κ_Ω), the minimum optimal-allocation mass (ρ_M), an

What carries the argument

The argument rests on a sharpness function φ that converts suboptimality gaps of the objective J_M(ω)=T(ω;M)^{-1} into distances to the optimal allocation set, and on a finite-time concentration result (Proposition 21) showing that empirical visitation frequencies track the running average of the estimated optimal allocations up to an error ℓ(t). The algorithm's sampling rule mixes the estimated optimal policy π*_t with a forcing policy π_f,t; the forcing schedule ε_t = 1/max{1,N_t(s_t)}^α guarantees coverage, while π*_t is the minimal-2-norm element of the estimated optimal allocation set Ω*_t(M_t). A chain of inequalities swaps between alternative sets Alt(M_t) and Alt(M) (Lemma 32) to low

Load-bearing premise

The two inequalities of Assumption 3 must hold, guaranteeing every optimal state-action allocation assigns positive mass to every state-action pair; if any optimal allocation puts zero mass on a pair, ρ_M = 0 makes the allocation-tracking error ξ_t blow up and the bound becomes vacuous.

What would settle it

Take a communicating, aperiodic discounted MDP with deterministic rewards, unique optimal policy, and transition densities in G_μ(L) satisfying Assumptions 1 and 2, but whose unique optimal allocation assigns zero probability to one state-action pair (so Assumption 3 fails). Run NaS (Algorithm 1) and check whether the empirical visitation frequency of that pair stays bounded away from the required coverage level, and whether the expected stopping time still satisfies E[τδ] ≤ inf{t : b(t,δ)<(t−√t)T(M)^{-1}−ℓ0(t,M)}+7 for small δ. A counterexample violating the bound would show the theorem's sco

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

If this is right

  • As δ shrinks, the bound recovers the asymptotically optimal coefficient T(M) exactly; for deterministic rewards the paper removes the factor-2 suboptimality present in the original NaS stopping rule.
  • Finite-confidence sample complexity is governed by the MDP's connectivity/mixing constants (m, η_m, κ_M, κ_Ω) and by the sharpness φ of the allocation objective, not just by the characteristic time.
  • The hyperparameters α and β of the forcing schedule appear in the correction exponents r_i, so they trade off coverage cost against allocation-tracking error in the non-asymptotic regime.
  • For any finite class of MDPs the objective is linearly sharp (Proposition 5), so the explicit bound of Corollary 10 applies broadly in practice.
  • The analysis accommodates non-unique optimal allocations directly by selecting the minimal-norm element of Ω*_t(M_t), avoiding the convex relaxations used in prior asymptotic work.

Where Pith is reading between the lines

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

  • If the dependencies on ρ_M and φ are tight, then instances where some optimal action is rarely needed, or where the allocation objective is nearly flat, are inherently harder at finite δ — a cost invisible to asymptotic analysis and likely present for any NaS-style tracking algorithm.
  • A testable extension: an algorithm that adapts ε_t to the estimated mixing rate (or that forgoes the minimal-norm selector when the optimal set is large) could reduce the sublinear corrections in ℓ0; the paper's bound offers a benchmark to evaluate such designs.
  • The paper's scope is limited by Assumption 3 to deterministic-reward MDPs where every optimal allocation is strictly positive; stochastic-reward settings, which avoid this degeneracy, are not covered by the main theorem.
  • The sharpness construction of Theorem 4 suggests that any algorithm driven by the plug-in objective will face arbitrarily slow allocation convergence near flat maxima; an algorithmic formulation that exploits easier approach paths to the optimal set could yield better finite-δ performance.

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

3 major / 5 minor

Summary. The paper studies fixed-confidence best policy identification (BPI) in discounted, tabular, single-trajectory MDPs with deterministic rewards. It analyzes a variant of the Navigate-and-Stop (NaS) algorithm and claims the first non-asymptotic sample-complexity upper bounds: an implicit bound (Theorem 6) involving a sublinear error term, and an explicit bound (Corollary 10) under a linear-sharpness assumption, with leading term T(M)log(1/δ). The analysis introduces finite-time concentration of empirical visitation frequencies, stability of optimal-allocation selectors under transition perturbation, and a sharpness function; Theorem 4 shows that the allocation objective can be arbitrarily flat along certain directions.

Significance. If the stated results are correct, this is a meaningful step beyond the purely asymptotic analysis of NaS: it identifies finite-confidence costs due to mixing, connectivity, forced exploration, and allocation geometry, and recovers the optimal leading constant T(M). The proof structure is elaborate and largely coherent, and the sharpness analysis (Theorem 4 and Proposition 5) is a useful standalone contribution. However, two central formal issues—the random-threshold formulation of the main bound and the absence of a proof of delta-correctness—together with the substantive nature of Assumption 3, prevent me from recommending acceptance in the current form.

major comments (3)
  1. [§2.2, Assumption 3 and Lemma 40] Assumption 3 is not a notational convenience: Lemma 40 uses its two strict inequalities to prove that every optimal allocation puts positive mass on every state-action pair, which is the only mechanism ensuring rho_M = min_{s,a} omega*(s,a) > 0. This rho_M appears in the denominator of xi_t (Eq. 6) and in constant A_3 of Corollary 10. There are communicating, aperiodic MDPs satisfying Assumptions 1–2 with a unique optimal policy and nonempty Alt(M) where a state-action pair is so dominated that omega*(s,a)=0; for such instances the stated guarantee collapses. The abstract and main theorems should explicitly restrict to Assumption-3 instances, or the analysis should be extended (e.g., via stochastic rewards as in [2]).
  2. [§3.1, Theorem 9, Appendix C] delta-PC correctness is asserted but not proved. The concentration events E1_T and E2_T are defined with lambda=1/T^2 (Definition 13) and are used only to bound the expected stopping time; no time-uniform argument shows that at the data-dependent stopping time the probability of outputting a suboptimal policy is at most delta. A direct union bound from Lemma 11 yields an extra SA log(SA/delta) term that is absent from the count-dependent threshold b(t,delta). The authors should provide the missing delta-PC proof or explicitly cite a lemma that calibrates the stopping threshold.
  3. [§4.2, Theorem 6 and Appendix C.6] The infimum in Theorem 6 uses b(t,delta), which is defined in Section 3.1 with the random counts N_t(s,a). The right-hand side is therefore a random variable, and the statement E[tau_delta] <= random inf + 7 is not a valid deterministic expected-complexity bound. The proof in C.6 splits the sum at a random T_thresh. This is repairable: replace b(t,delta) with the deterministic upper bound \bar b(t,delta) = log(1/delta)+S^2 A log(2et), as already used in Corollary 34, and derive E[tau] <= \bar T_thresh + 7. The main theorem should be restated with this deterministic threshold.
minor comments (5)
  1. [Theorem 26, Eq. (13)] The inequality in Eq. (13) has the wrong direction: for t < tau_delta the stopping inequality is t T(N_t/t; M_t)^{-1} < b(t,delta), not >=. The intended chain is recovered by writing b(t,delta) > t T(...) >= ..., but the text should be corrected.
  2. [Theorem 26 vs Lemmas 27–29] The sign convention for ell_1, ell_2, ell_3 is inconsistent: Theorem 26 defines them as positive quantities in a lower bound with a minus sign, while Lemmas 27–29 define the same names as negative errors. Please unify the notation.
  3. [Corollary 10, constant A_2] In the plain-text rendering, A_2 appears as 'log(L)(eL + kappa_M)eL'; this should be \tilde L, not a new factor exp(1)*L. Please ensure the typesetting is unambiguous.
  4. [Algorithm 1, line 2] There is a stray 'and observes 1' at the end of line 2. Remove it.
  5. [Appendix C.6, Eq. (60)] The symbols beta(t,delta) and b(t,delta) are used interchangeably; pick one notation and distinguish the random threshold from the deterministic upper bound used later.

Circularity Check

0 steps flagged

No circularity: the bound is derived from concentration and threshold inversion, not from definitional identity or fitted inputs.

full rationale

I walked the derivation chain from Theorem 6 back through Theorem 26 and the accompanying lemmas. The claimed bound is not the algorithm's stopping rule restated: Theorem 26 lower-bounds the stopping statistic at any time before stopping by (t - sqrt(t)) T(M)^{-1} minus explicit error terms, using finite-time tracking of visitation frequencies (Proposition 21), stability of the minimum-norm allocation selector (Lemma 16 / Lemma 46), Lipschitzness of KL and feasible-set stability under Assumption 2 (Lemmas 36 and 47), and the alternative-set swapping argument (Lemma 32). The error term ell_0 is then bounded in terms of instance constants (m, eta_m, kappa_M, kappa_Omega, rho_M, the sharpness function phi_M, and hyperparameters alpha, beta, L). None of these quantities is fitted to data or defined to contain the target result; the sharpness function is an honest input, and Theorem 4 explicitly shows it can be arbitrarily bad. The transition from the implicit bound to the explicit Corollary 10 is a standard algebraic inversion of t <= T(M) b(t,delta) + sqrt(t) + T(M) ell_0(t), with all sublinear powers evaluated at the leading scale B_delta. The paper's self-citations, most notably [27] by one of the current authors, are used for algorithmic motivation and for proof templates, but the relevant results are re-proved in the appendix (e.g., Lemma 12, Proposition 19, Lemma 17), so they are not load-bearing. Assumption 3 restricts the scope to MDPs where every optimal allocation is fully supported; the paper itself describes this as a way to avoid degenerate cases and acknowledges that stochastic rewards could handle the same issue. That is a limitation of the theorem's coverage, not a circular step: the validity of the bound on the restricted class is still derived from independent concentration and stability arguments rather than from assuming the conclusion.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 0 invented entities

The central claim rests on three domain assumptions restricting the MDP class, one ad-hoc smoothness condition for the explicit corollary, the algorithm's three free hyperparameters, and standard concentration/perturbation results. The sharpness function φ_M is a definition with generic existence (Appendix D.2 constructs it), not a postulated entity; instance constants (κ_M, L̃, κ_Ω, ρ_M, m, η_m) are determined by the true MDP rather than fitted. No parameter is fitted to data and no entity is invented.

free parameters (4)
  • α (exploration exponent)
    Hyperparameter of the ε_t = 1/max{1+ν, N_t(s_t)}^α forcing schedule; must satisfy α∈(0,1) and α+β<1; appears in every exponent r_i of the explicit bound. Chosen by hand, not fitted.
  • β (forcing-softmax exponent)
    Hyperparameter in π_f,t(a|s) = softmax(−β_t(s)N_t(s,·)); β∈(0,1) chosen by hand; controls how aggressively under-sampled actions are forced.
  • ν (exploration offset)
    Offset in ε_t = 1/max{1+ν, N_t(s_t)}^α; ν∈(0,1) ensures the exploration term is well-behaved at t=1; appears implicitly in the visitation lower bound (Lemma 12).
  • C_φ (linear sharpness constant)
    Corollary 10 requires φ_M(x) ≤ C_φ x; C_φ is instance-dependent and not computed in the paper. The implicit Theorem 6 instead requires the full sharpness function φ_M. This is an input to the theorem, not derived.
axioms (5)
  • domain assumption Communicating MDP with unique optimal policy; aperiodic under a policy assigning positive probability to all actions (Assumption 1)
    Restricts the instance class; needed for geometric mixing, for well-defined ω*, and for the perturbation bounds on stationary distributions (Lemma 39).
  • domain assumption Known reference measure μ with density ratios dμ/dQ ∈ [1/L, L] for all transitions (Assumption 2)
    Yields uniform KL bounds (KL ≤ 2log L, used in ℓ1) and mutual absolute continuity across the model class, which is required for the alternative-set swap in Lemma 32 and the Lipschitz property in Lemma 36.
  • ad hoc to paper Value-function inequalities of Assumption 3 (strict dominance conditions on Q^{π*}(s,a) and on the optimal-policy transitions)
    Ensures every optimal allocation is strictly positive (Lemma 40), so ρ_M > 0. The paper admits this is 'to avoid notation cluttering' and that [2] instead uses stochastic rewards, meaning the theorem as stated covers only instances satisfying this technical condition.
  • ad hoc to paper Linear sharpness φ_M(x) ≤ C_φ x for the explicit bound (Corollary 10)
    The clean Bδ + Õ(...) form holds only under this condition. Theorem 4 constructs families with polynomial sharpness exponent (m−n)/m for arbitrary m>n≥1, i.e., arbitrarily flat objectives; Proposition 5 restores linear sharpness for finite MDP families.
  • standard math Standard concentration and perturbation results: Pinsker, Azuma–Hoeffding, Doob's inequality, Hoffman's error bound, Berge's maximum theorem, Markov-chain stationary-distribution perturbation bounds [8, 29]
    Invoked throughout Appendices C–D as unproved background; Lemma 39 (perturbation bound) is imported from the cited literature.

pith-pipeline@v1.3.0-alltime-deepseek · 53042 in / 30278 out tokens · 247963 ms · 2026-08-01T18:44:53.610714+00:00 · methodology

0 comments
read the original abstract

In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning. This is an active sequential hypothesis testing problem in which the learner's objective is to identify an optimal policy in a Markov Decision Process (MDP) with high confidence, while minimizing the expected sample complexity to do so. We consider an online setting with deterministic rewards, where the agent must strategically navigate through the MDP in order to effectively explore. Previous works in the literature have provided asymptotically optimal methods for BPI, such as the Navigate and Stop (NaS) algorithm and its variants, however existing analysis remains asymptotic. In this work, we fill that gap by providing the first non-asymptotic sample complexity guarantees for NaS, showing that its sample complexity depends not only on the characteristic time, but also on the connectivity of the underlying MDP, the curvature of the optimal characteristic time, and other instance-dependent quantities. We identify these additional attributes and make explicit their contributions to the overall sample complexity.

Figures

Figures reproduced from arXiv: 2607.17201 by Aldo Pacchiano, Alessio Russo, Joseph Lazzaro.

Figure 1
Figure 1. Figure 1: Empirical sharpness scaling for the MDP family of Theorem 4. For each choice of integers [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Visualization of the family of MDPs used in the construction in Proposition 52. We display [PITH_FULL_IMAGE:figures/full_fig_p056_2.png] 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

37 extracted references · 1 canonical work pages

  1. [1]

    Al Marjani and A

    A. Al Marjani and A. Proutiere. Adaptive sampling for best policy identification in markov decision processes. InInternational Conference on Machine Learning, pages 7459–7468. PMLR, 2021

    2021

  2. [2]

    Al Marjani, A

    A. Al Marjani, A. Garivier, and A. Proutiere. Navigating to the best policy in markov decision processes. InAdvances in Neural Information Processing Systems, volume 34, pages 25852– 25864, 2021

    2021

  3. [3]

    Ariu, P.-A

    K. Ariu, P.-A. Wang, A. Proutiere, and K. Abe. Policy testing in markov decision processes. arXiv preprint arXiv:2505.15342, 2025

    Pith/arXiv arXiv 2025

  4. [4]

    Berge.Topological Spaces: Including a Treatment of Multi-Valued Functions, Vector Spaces, and Convexity

    C. Berge.Topological Spaces: Including a Treatment of Multi-Valued Functions, Vector Spaces, and Convexity. Courier Corporation, 1997

    1997

  5. [5]

    Boone and O.-A

    V . Boone and O.-A. Maillard. The regret lower bound for communicating Markov Decision Processes. InarXiv preprint arXiv:2501.13013, 2025

    Pith/arXiv arXiv 2025

  6. [6]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart.Concentration inequalities : a non asymptotic theory of independence. Oxford University Press, 2013. URL https://inria.hal.science/ hal-00942704

    2013

  7. [7]

    A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for markov decision processes. Mathematics of Operations Research, 22(1):222–255, 1997. ISSN 0364765X, 15265471. URL http://www.jstor.org/stable/3690147

    arXiv 1997

  8. [8]

    G. E. Cho and C. D. Meyer. Comparison of perturbation bounds for the stationary distribution of a Markov chain.Linear Algebra and its Applications, 335(1):137–150, 2001. ISSN 0024-3795. doi: 10.1016/S0024-3795(01)00320-2

    work page doi:10.1016/s0024-3795(01)00320-2 2001

  9. [9]

    T. M. Cover and J. A. Thomas.Elements of Information Theory (Wiley Series in Telecommuni- cations and Signal Processing). Wiley-Interscience, USA, 2006. ISBN 0471241954

    2006

  10. [10]

    C. Dann, T. Lattimore, and E. Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning.Advances in Neural Information Processing Systems, 30, 2017. 10

    2017

  11. [11]

    Degenne and W

    R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers.Advances in Neural Information Processing Systems, 32, 2019

    2019

  12. [12]

    Degenne, W

    R. Degenne, W. M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. Advances in Neural Information Processing Systems, 32, 2019

    2019

  13. [13]

    Garivier and E

    A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998–1027. PMLR, 2016

    2016

  14. [14]

    Garivier, P

    A. Garivier, P. Ménard, L. Rossi, and P. Menard. Thresholding bandit for dose-ranging: The impact of monotonicity.arXiv preprint arXiv:1711.04454, 2017

    Pith/arXiv arXiv 2017

  15. [15]

    A. J. Hoffman. On approximate solutions of systems of linear inequalities.Journal of research of the National Bureau of Standards, 49:263, 1952

    1952

  16. [16]

    Jonsson, E

    A. Jonsson, E. Kaufmann, P. Ménard, O. Darwiche Domingues, E. Leurent, and M. Valko. Planning in markov decision processes with gap-dependent sample complexity.Advances in Neural Information Processing Systems, 2020

    2020

  17. [17]

    Jourdan and A

    M. Jourdan and A. Azize. Optimal best arm identification under differential privacy.arXiv preprint arXiv:2510.17348, 2025

    arXiv 2025

  18. [18]

    Jourdan, R

    M. Jourdan, R. Degenne, and E. Kaufmann. An epsilon-best-arm identification algorithm for fixed-confidence and beyond.Advances in Neural Information Processing Systems, 36: 16578–16649, 2023

    2023

  19. [19]

    Kaufmann, P

    E. Kaufmann, P. Ménard, O. Darwiche Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive reward-free exploration. In V . Feldman, K. Ligett, and S. Sabato, editors,Proceed- ings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 865–891. PMLR, 16–19 Mar 2021. URL https://...

    2021

  20. [20]

    Lazzaro and C

    J. Lazzaro and C. Pike-Burke. Fixed-confidence multiple change point identification under bandit feedback. InProceedings of the 42nd International Conference on Machine Learning, 2025

    2025

  21. [21]

    J. Ok, A. Proutiere, and D. Tranos. Exploration in structured reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, ed- itors,Advances in neural information processing systems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/ d693d554e0ede0d75f...

    2018

  22. [22]

    Poiani, M

    R. Poiani, M. Bernasconi, and A. Celli. Non-asymptotic analysis of (sticky) track-and-stop. arXiv preprint arXiv:2505.22475, 2025

    arXiv 2025

  23. [23]

    Poiani, M

    R. Poiani, M. Bernasconi, and A. Celli. Pure exploration with infinite answers.arXiv preprint arXiv:2505.22473, 2025

    arXiv 2025

  24. [24]

    M. L. Puterman.Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014

    2014

  25. [25]

    Russo and A

    A. Russo and A. Pacchiano. Adaptive exploration for multi-reward multi-policy evaluation. arXiv preprint arXiv:2502.02516, 2025

    Pith/arXiv arXiv 2025

  26. [26]

    Russo and A

    A. Russo and A. Proutiere. Model-free active exploration in reinforcement learning. InAdvances in Neural Information Processing Systems, volume 36, pages 54740–54753, 2023

    2023

  27. [27]

    Russo and F

    A. Russo and F. Vannella. Multi-reward best policy identification. InAdvances in Neural Information Processing Systems, volume 37, pages 105583–105662, 2024

    2024

  28. [28]

    Russo, Y

    A. Russo, Y . Song, and A. Pacchiano. Pure exploration with feedback graphs.arXiv preprint arXiv:2503.07824, 2025

    Pith/arXiv arXiv 2025

  29. [29]

    P. J. Schweitzer. Perturbation theory and finite markov chains.Journal of Applied Probability, 5(2):401–413, 1968. ISSN 00219002. 11

    1968

  30. [30]

    Sethi, K

    A. Sethi, K. S. Sagar, S. Agrawal, D. Basu, and P. Karthik. Asymptotically optimal sequential testing with markovian data.arXiv preprint arXiv:2602.17587, 2026

    Pith/arXiv arXiv 2026

  31. [31]

    R. K. Sundaram.A First Course in Optimization Theory. Cambridge University Press, Cam- bridge, 1996

    1996

  32. [32]

    R. S. Sutton and A. G. Barto.Reinforcement learning: An introduction. MIT press, 2018

    2018

  33. [33]

    Taupin, Y

    J. Taupin, Y . Jedra, and A. Proutiere. Best policy identification in linear mdps. In2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1–8. IEEE, 2023

    2023

  34. [34]

    Tuynman and R

    A. Tuynman and R. Degenne. The batch complexity of bandit pure exploration. InICML 2025-42nd International Conference on Machine Learning, volume 267, pages 60442–60468, 2025

    2025

  35. [35]

    Zalinescu

    C. Zalinescu. Sharp estimates for hoffman’s constant for systems of linear inequalities and equalities.SIAM Journal on Optimization, 2006. 12 Appendix Contents 1 Introduction 1 2 Problem Setting 2 2.1 Sample Complexity Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

    2006

  36. [36]

    The function f ⋆ is a continuous function on X and ψ⋆ is a compact-valued upper-hemi- continuous correspondence onX

  37. [37]

    Lemma 42.Let Ω⋆(M) := ( ω∈Ω(M) inf M′∈Alt(M) X s,a ω(s, a)KL(P(s, a), P′(s, a)) = (T⋆(M))−1 )

    If f is concave on X × Y, and ψ has a convex graph, then f ⋆ is a concave function and ψ⋆ is a convex-valued upper-hemi-continuous correspondence. Lemma 42.Let Ω⋆(M) := ( ω∈Ω(M) inf M′∈Alt(M) X s,a ω(s, a)KL(P(s, a), P′(s, a)) = (T⋆(M))−1 ) . Then the set of optimizersΩ ⋆(M)is convex. Proof. The idea of the proof is to apply twice Berge’s maximum Theorem ...

    1994