Research map / Reinforcement learning / MDPs and planning

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Offline RL sample complexity · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first non-asymptotic (finite-confidence) sample-complexity upper bounds for the Navigate-and-Stop algorithm for best policy identification in single-trajectory tabular discounted MDPs with deterministic rewards.

Problem

Best Policy Identification in online tabular RL under navigation constraints (single trajectory) has only asymptotic (delta to 0) sample-complexity guarantees for Navigate-and-Stop; finite-confidence behavior is unknown.

Approach

Analyzes the original NaS algorithm (with a modified forcing schedule and set-valued optimal allocations with minimum-norm selector) non-asymptotically, using concentration of visitation frequencies under adaptive non-homogeneous Markov dynamics, and a sharpness function for the allocation objective, yielding an implicit and explicit finite-delta bound depending on connectivity, mixing, forcing an

Key results

• Proves an implicit non-asymptotic bound E[tau] <= inf{t: b(t,delta) < (t - sqrt(t)) T(M)^{-1} - l_0(t,M)} + 7 for NaS, with l_0 sublinear in t, recovering asymptotic optimality limsup E[tau]/log(1/delta) <= T(M).
• Under linear sharpness, obtains explicit bound E[tau] <= B_delta + O~(sqrt(B_delta) + T(M) sum_i A_i B_delta^{r_i}) with all r_i < 1.
• Shows the sharpness exponent of the allocation objective can be arbitrarily small: for any m>n>=1 there is an MDP with local polynomial sharpness exponent (m-n)/m; finite MDP families give linear sharpness.

Surprising findings

• The objective J_M can be arbitrarily flat near optimal allocations, so small model-estimation errors can cause large allocation errors.
• Under deterministic rewards, NaS attains the exact leading constant, whereas the original NaS analysis was suboptimal by a factor of 2 due to separate reward and transition stopping.

Limitations

• Modifies the forcing schedule and stopping analysis; the bound is implicit and contains many instance-dependent constants with unspecified tightness.
• Restricted to tabular, deterministic-reward, communicating MDPs with unique optimal policy and bounded transition ratio (Assumption on G_mu(L)).
• Algorithm is noted as computationally expensive and not practically deployable.

Experimental setup

Metrics: expected sample complexity upper bound

Baselines: Navigate-and-Stop

Builds on: Navigate-and-Stop Track-and-Stop forcing policy exploration (Russo-style forcing / Mukherjee et al.) generalized likelihood ratio stopping

Closest papers by meaning

• Multi-Reward Best Policy Identification (NeurIPS 2024 · similarity 0.91)
• Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
• Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.90)
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.89)
• Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.89)
• Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.88)