Actor-Critics Can Achieve Optimal Sample Efficiency

Kevin Tan; Wei Fan; Yuting Wei

REVIEW 3 major objections 4 minor 2 cited by

Actor-Critics Can Achieve Optimal Sample Efficiency

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read An actor-critic algorithm achieves optimal $1/\epsilon^2$ sample efficiency under general function approximation when strategic exploration is needed.

desk verdict The paper's main theorem is unproven: the optimism argument applies completeness to a pointwise envelope that need not belong to F, so the claimed 1/ε² guarantee currently rests on a gap. read the letter →

arxiv 2505.03710 v1 pith:DZCZS6GJ submitted 2025-05-06 stat.ML cs.AIcs.LG

Kevin Tan , Wei Fan , Yuting Wei This is my paper · ORCID

classification stat.MLcs.AIcs.LG MSC 68Q3268T0590C40

keywords actor-criticalgorithmssamplecomplexityregretboundsgeneralfunctionapproximationoptimisticexplorationrare-switchinghybridreinforcementlearningBellmaneluderdimension

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 to resolve an open problem in reinforcement learning: no actor-critic algorithm with general function approximation was previously known to find an $\epsilon$-optimal policy with $O(1/\epsilon^2)$ sampled trajectories when the agent must explore strategically. It introduces NORA, an optimistic actor-critic that learns an off-policy critic targeting the optimal value function $Q^*$, updates the critic only rarely, and resets the actor policy after each critic update. Under standard realizability and completeness assumptions and a bounded Bellman eluder dimension, NORA achieves $O(\sqrt{dH^5T\log T\log|\mathcal{A}|} + \sqrt{\beta H^4T \,\mathrm{SEC}(\mathcal{F},\Pi,T)})$ regret, which translates into the desired $1/\epsilon^2$ sample complexity. The paper further shows that adding offline data yields a non-optimistic hybrid actor-critic with $\sqrt{T}$ regret when the offline dataset satisfies a single-policy concentrability condition. If correct, these results constitute the first optimal-rate guarantee for policy-based methods in this regime.

What carries the argument

The load-bearing mechanism is the switch from a critic that targets the current policy $\pi^{(t)}$ to one that targets the optimal value $Q^*$, combined with a rare-switching schedule. This makes the Bellman operator time-invariant, so the auxiliary class needed for completeness shrinks from $(T\Pi)^T\mathcal{F}$ to $\mathcal{T}\mathcal{F}$, and the log-covering number no longer grows with the number of actor updates. The number of critic updates is controlled by the squared distributional Bellman eluder dimension, the largest $d$ such that a sequence of Bellman errors can be extrapolated from past data; the paper shows at most $O(dH\log T)$ updates occur. Policy resets to uniform after each update compensate for the actor lagging behind the changing greedy policy, and the higher learning rate absorbs the extra reset cost. The mirror-ascent update $\pi^{(t+1)}_h(\cdot|s)\propto \pi^{(t)}_h(\cdot|s)\exp(\eta f^{(t)}_h(s,\cdot))$ is what converts the critic values into a tractable tracking-error bound.

What would settle it

Run NORA on an MDP with a function class $\mathcal{F}$ that contains $Q^*$ but is not closed under Bellman backups, and log the pointwise optimism check $f^{(t)}_h(s,a) \ge (T f^{(t)}_{h+1})(s,a)$ on every visited state-action pair at every update; a single violation on a reachable pair, or a number of critic updates growing linearly in $T$ instead of $O(dH\log T)$, would contradict Lemma 14 and hence Theorem 2.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that strategic exploration in actor-critic methods with general function approximation can be made statistically optimal by having the critic target $Q^*$ rather than the value of the current policy. NORA maintains a confidence set of critics whose squared temporal-difference error is close to minimal, plays the optimistic upper envelope $f^{(t)}_h(s,a)=\sup_{f\in\mathcal{F}^{(t_{\mathrm{last}})}} f_h(s,a)$, and updates the policy by multiplicative-weights mirror ascent. Because the Bellman backup of any $\mathcal{F}$-function under the greedy operator lies in the auxiliary class $\mathcal{T}\mathcal{F}$, the confidence set admits $T^\pi_h f^{(t)}_{h+1}$, so Lemma 14 gives optimism $f^{(t)}_h \ge T^\pi_h f^{(t)}_{h+1}$ for every $\pi$; the negative Bellman error term in the regret decomposition is then nonpositive. Rare-switching keeps the number of critic updates at $O(dH\log T)$, and policy resets plus an enlarged learning rate control the tracking error of the actor relative to the greedy policy $\pi_{f^{(t)}}$. The result is the regret bound in Theorem 2 and sample complexity $N\ge \Omega(dH^5\log T\log|\mathcal{A}|/\epsilon^2 + H^4\beta\,\mathrm{SEC}(\mathcal{F},\Pi,T)/\epsilon^2)$.

Load-bearing premise

The argument's load-bearing premise is generalized completeness: the critic's function class must be rich enough that every one-step look-ahead value computed from any critic it contains is again representable in the auxiliary class; if even one such look-ahead value falls outside the class, the optimism inequality that makes the negative Bellman error vanish can fail.

Editorial extensions

If this is right

Actor-critic algorithms with general function approximation can reach $\tilde{O}(\sqrt{T})$ regret and $1/\epsilon^2$ sample complexity without reachability or coverage assumptions, matching the best rates previously known only in tabular or linear settings.
Targeting $Q^*$ instead of $Q^{\pi^{(t)}}$ keeps optimism valid under rare critic updates, so delayed or slowly updated critics do not destroy the exploration guarantee.
The policy-reset trick limits the cost of reacting to rare critic updates to $O(dH\log T)$, which is dominated by the main $\sqrt{T}$ regret term.
With offline data satisfying a single-policy concentrability bound, optimism can be dropped entirely while retaining $\sqrt{T}$ regret, provided $N_{\mathrm{off}}\ge c^*_{\mathrm{off}}dH^4/\epsilon^2$.
Hybrid data can be partitioned into offline and online regions, and the regret bound improves when offline coverage is good, giving a formal sense in which offline pretraining accelerates online actor-critic fine-tuning.

Reading between the lines

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

If the rare-switching insight transfers to practice, deep actor-critic implementations should update the critic only when the temporal-difference error moves a confidence bound, and reset or reinitialize the policy after large critic changes; this could reconcile the success of delayed-target tricks in DDPG and TD3 with theory.
The dependence on $\mathcal{T}\mathcal{F}$ completeness suggests that expressive, closed-under-Bellman-backup function classes, such as sufficiently wide networks or classes with built-in value-iteration layers, may be needed to realize the rate in practice; otherwise the optimism step can fail silently.
A direct testable prediction of the theory is that NORA's regret should scale as the square root of the Bellman eluder dimension times the horizon and $T$, and that removing any one ingredient—optimism, rare switching, or policy resets—should degrade the bound.
In the hybrid setting, the theory predicts a smooth trade-off: as more offline data accumulates, the required size of the online exploration region shrinks, so the same total regret can be achieved with fewer online samples; this is a concrete prescription for offline-to-online fine-tuning schedules.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Kevin, Wei, and Yuting's paper makes a bold claim: an actor-critic with general function approximation achieving 1/ε² sample complexity and √T regret. The architecture—rare-switching, Q*-targeting critic, policy resets, with SEC/Bellman-eluder complexity—is a plausible and natural resolution of an open problem. The hybrid RL extensions are also thoughtful. Credit where due: the problem selection is good, and the regret decomposition is standard and mostly carefully written. The paper is not a rehash.

The problem is in the optimism argument, and it is load-bearing. Algorithm 2 (and Algorithm 1, for that matter) chooses f^(t)_h(s,a) = argmax_{f∈F(t_last)} f_h(s,a) pointwise. That is the upper envelope of the confidence set, not necessarily a member of F. Lemma 14 then applies Lemma 17 to f^(t), using Assumption 2 (G = TF) to claim T f^(t) ∈ F(t_last). But Assumption 2 only covers Bellman backups of functions in F. For linear classes, the envelope is not in F; it is in a larger class. Lemma 17's premise fails, and with it the optimism step f^(t) ≥ T^π f^(t+1), the nonpositivity of the negative Bellman error term, and the final regret bound. The same issue appears in Lemma 7 for Algorithm 1, so the "easy case" is affected too, though that one can be repaired by the closure-under-truncated-sums assumption that the authors introduce for the policy class.

The reader's report flagged uncertainty around completeness; the stress-test pinpoints the sharper failure. I agree with the reader's conditional verdict, but I would go further: as written, Theorem 2 is unproven. The fix is not obvious, since assuming F closed under pointwise suprema would rule out linear classes and make the result much less interesting. The authors need to either change the algorithm so the selected optimistic function lies in F, or add a completeness assumption covering the envelope class.

Other soft spots are minor: Lemma 25's statement is ambiguous as noted, Lemma 2 has a misstated covering number, and the "optimal" in the title overclaims—no lower bound specific to actor-critics is proven. These don't matter much next to the main gap.

If the optimism gap is fixed, this could be a strong paper. As it stands, it deserves a serious referee—the idea is important enough to be worth the effort—but it needs major revision. I would not cite the main theorem in its current form.

Referee Report

3 major / 4 minor

Summary. The paper studies finite-horizon episodic reinforcement learning with general function approximation and proposes optimistic actor-critic algorithms. As a warm-up, DOUHUA (Algorithm 1) is shown to achieve sqrt(T)-type regret when the policy class does not grow too fast, e.g., under closure under truncated sums. The main contribution is NORA (Algorithm 2), which targets Q*, performs rare-switching critic updates, uses policy resets, and is claimed to achieve regret O(sqrt(dH^5 T log T log|A|) + dH^3 log T + sqrt(beta H^4 T SEC(F,Pi,T))), corresponding to O(1/epsilon^2) sample complexity without reachability or coverage assumptions. The paper also gives hybrid-RL extensions: a non-optimistic algorithm NOAH (Algorithms 3 and 4) using offline data, and an optimistic hybrid version (Algorithm 5). Numerical experiments on a linear-MDP Tetris task and a deep hybrid-RL benchmark are reported.

Significance. If correct, the paper would resolve a well-known open problem: it would be the first actor-critic method with general function approximation and strategic exploration to achieve 1/epsilon^2 sample complexity and sqrt(T)-type regret. The rare-switching/reset mechanism and the hybrid-RL analysis are interesting and potentially reusable. The paper is also careful to position itself against prior work and provides extensive appendices plus reproducibility details for the experiments. However, the central Theorem 2 rests on an optimism proof that is invalid as written, because the pointwise-max critic lies outside the function class to which the completeness and concentration lemmas apply. This is a load-bearing gap that also affects the switching-cost lemma and the optimistic hybrid theorem, so the contribution is not established in its current form.

major comments (3)

[§4.2, Algorithm 2 (line 4); Lemma 14 (Appendix B.5.2)]
[Appendix B.5.1, Lemma 13]
[§5.2, Algorithm 5 and Theorem 5]

minor comments (4)

[Lemma 2]
[Lemma 25]
[Definition 4 and Theorem 4]
[Assumption 3 and abstract]

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: NORA's regret bound is derived from external complexity measures and standard RL lemmas; self-citations are limited to non-load-bearing hybrid-RL extensions.

full rationale

The derivation of the main result (Theorem 2) is self-contained. It uses a value-difference decomposition (Lemma 8), mirror-descent tracking bounds (Lemmas 9 and 12), a switch-count bound via the Bellman eluder dimension (Lemma 13), optimism from completeness (Lemma 14), and an SEC-based Bellman-error bound (Lemma 11). The SEC and Bellman eluder dimension are external complexity measures; beta is a confidence width derived from covering numbers of F and TF, not a fitted quantity. No equation in the proof is equivalent by construction to the claimed regret bound, and no fitted parameter is renamed as a prediction. Self-citations to Tan et al. (2024) and Tan and Xu (2024) occur only in the hybrid-RL motivation and in proof-by-analogy for the hybrid extensions (Appendices C.2-C.3 and Lemmas 15-16); they are not needed for Theorem 2 and are therefore not load-bearing. A separate mathematical concern is that Algorithm 2 defines f^(t) as a pointwise argmax over F(tlast), which need not lie in F, so the completeness premise of Lemma 14 is not formally justified; this is an unproven closure condition, not a circular reduction, and does not affect the circularity score.

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

No data-fitted constants appear in the derivation; learning rate eta and confidence width beta are set to explicit closed forms. The main axes are standard complexity measures, SEC, Bellman eluder dimension, and concentrability. The symmetric function class condition is stated only inside the hybrid proofs, and no new entities are postulated.

assumptions (7)

domain assumption Realizability: Q*_h in F_h for all h (Assumption 1).
The critic class must contain the optimal Q-function; used in all main theorems.
domain assumption Generalized completeness: G contains every Bellman backup T f, with G = T F for NORA (Assumption 2).
Ensures T f is representable, so confidence sets contain T f and optimism in Lemma 14 holds. This is the weakest load-bearing premise.
domain assumption Bounded D_delta-type Bellman eluder dimension d < infinity (Assumption 3).
Bounds the number of NORA critic updates by O(dH log T) in Lemma 13; without it, the policy-reset cost is uncontrolled.
domain assumption Finite single-policy concentrability c*_off for Theorems 3 and 4.
The offline-data error term scales with c*_off; the bound is vacuous if coverage is unbounded.
domain assumption Finite partial all-policy concentrability for Theorem 5.
Needed to bound the offline portion of the Bellman error in the hybrid regret decomposition.
domain assumption Symmetric function class: -f in F for all f in F.
Invoked in Appendices C.1 and C.2 for Theorems 3 and 4 and not listed in the theorem statements; should be added or removed.
ad hoc to paper Closure under truncated sums (Definition 3) for Corollary 1.
Used only for the good-case DOUHUA bound, not for the main NORA claim.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Actor-Critics Can Achieve Optimal Sample Efficiency." pith.science (2026). https://pith.science/paper/DZCZS6GJ

@misc{pith2026250503710,
  author       = {Pith},
  title        = {Pith review of: Actor-Critics Can Achieve Optimal Sample Efficiency},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DZCZS6GJ}},
  note         = {Machine review of arXiv:2505.03710}
}

abstract

Actor-critic algorithms have become a cornerstone in reinforcement learning (RL), leveraging the strengths of both policy-based and value-based methods. Despite recent progress in understanding their statistical efficiency, no existing work has successfully learned an $\epsilon$-optimal policy with a sample complexity of $O(1/\epsilon^2)$ trajectories with general function approximation when strategic exploration is necessary. We address this open problem by introducing a novel actor-critic algorithm that attains a sample-complexity of $O(dH^5 \log|\mathcal{A}|/\epsilon^2 + d H^4 \log|\mathcal{F}|/ \epsilon^2)$ trajectories, and accompanying $\sqrt{T}$ regret when the Bellman eluder dimension $d$ does not increase with $T$ at more than a $\log T$ rate. Here, $\mathcal{F}$ is the critic function class, $\mathcal{A}$ is the action space, and $H$ is the horizon in the finite horizon MDP setting. Our algorithm integrates optimism, off-policy critic estimation targeting the optimal Q-function, and rare-switching policy resets. We extend this to the setting of Hybrid RL, showing that initializing the critic with offline data yields sample efficiency gains compared to purely offline or online RL. Further, utilizing access to offline data, we provide a \textit{non-optimistic} provably efficient actor-critic algorithm that only additionally requires $N_{\text{off}} \geq c_{\text{off}}^*dH^4/\epsilon^2$ in exchange for omitting optimism, where $c_{\text{off}}^*$ is the single-policy concentrability coefficient and $N_{\text{off}}$ is the number of offline samples. This addresses another open problem in the literature. We further provide numerical experiments to support our theoretical findings.

Figures

Figures reproduced from arXiv: 2505.03710 by the authors.

**Figure 2.** Per-episode reward of Algorithms 1 and 2, compared to a rare-switching version of LSVI-UCB (Jin [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

**Figure 3.** Cumulative regret of Algorithms 1 and 2 vs. LSVI-UCB (Jin et al., 2019) on Tetris. This setting [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Hybrid RL experiment on the antmaze-medium-diverse-v2 task. Comparison of Alg. 1H, Alg. 2H, and Cal-QL (Nakamoto et al., 2023) with offline pretraining. Alg. 2H uses approximate optimism via action sampling and outperforms both Cal-QL and Alg. 1H, despite no pessimism.…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL
cs.LG 2025-06 conditional novelty 6.0 of 10

VAC is a new actor-critic method with a single optimistic objective and a provably near-optimal regret bound in linear Markov decision processes.
Statistical and Algorithmic Foundations of Reinforcement Learning
stat.ML 2025-07 accept

A tutorial collecting minimax sample complexity results for tabular RL across generative model, online, offline, robust, and human-feedback settings.

Reference graph

Works this paper leans on

63 extracted references · 52 canonical work pages · cited by 2 Pith papers

[1]

Abbasi-Yadkori, Y., Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C., and Weisz, G. (2019). POLITEX : Regret bounds for policy iteration using expert prediction. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 3692--3702. PMLR

work page 2019
[2]

Agarwal, A., Henaff, M., Kakade, S., and Sun, W. (2020). Pc-pg: Policy cover directed exploration for provable policy gradient learning

work page 2020
[3]

Agarwal, A., Jin, Y., and Zhang, T. (2022). Vo q l: Towards optimal regret in model-free rl with nonlinear function approximation

work page 2022
[4]

M., Lee, J

Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research , 22(98):1--76

2021
[5]

J., Jiang, N., Sekhari, A., and Xie, T

Amortila, P., Foster, D. J., Jiang, N., Sekhari, A., and Xie, T. (2024). Harnessing density ratios for online reinforcement learning

work page 2024
[6]

and Russo, D

Bhandari, J. and Russo, D. (2022). Global optimality guarantees for policy gradient methods

work page 2022
[7]

Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2024). Provably efficient exploration in policy optimization

work page 2024
[8]

and Rosenberg, A

Cassel, A. and Rosenberg, A. (2024). Warm-up free policy optimization: Improved regret in linear markov decision processes

work page 2024

Show all 63 references

[9]

Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2022). Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research , 70(4):2563--2578

2022
[10]

J., Yuan, A., Gu, Q., and Jordan, M

Chen, Z., Li, C. J., Yuan, A., Gu, Q., and Jordan, M. I. (2022). A general framework for sample-efficient function approximation in reinforcement learning

2022
[11]

and Theja Maguluri, S

Chen, Z. and Theja Maguluri, S. (2022). Sample complexity of policy-based methods under off-policy sampling and linear function approximation. In Camps-Valls, G., Ruiz, F. J. R., and Valera, I., editors, Proceedings of The 25th International Conference on Artificial Intelligen...

2022
[12]

and Barto, A

Crites, R. and Barto, A. (1994). An actor/critic algorithm that is equivalent to q-learning. In Tesauro, G., Touretzky, D., and Leen, T., editors, Advances in Neural Information Processing Systems , volume 7. MIT Press

1994
[13]

Efroni, Y., Shani, L., Rosenberg, A., and Mannor, S. (2020). Optimistic policy optimization with bandit feedback

2020
[14]

Fujimoto, S., van Hoof, H., and Meger, D. (2018). Addressing function approximation error in actor-critic methods

2018
[15]

S., Wang, D., and Aggarwal, V

Gaur, M., Bedi, A. S., Wang, D., and Aggarwal, V. (2024). Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization

2024
[16]

Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor

2018
[17]

He, J., Zhao, H., Zhou, D., and Gu, Q. (2023). Nearly minimax optimal reinforcement learning for linear markov decision processes

2023
[18]

Huang, Y., Jia, Y., and Zhou, X. Y. (2024). Sublinear regret for a class of continuous-time linear--quadratic reinforcement learning problems

2024
[19]

Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2016). Contextual decision processes with low bellman rank are pac-learnable

2016
[20]

Jin, C., Liu, Q., and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms

2021
[21]

Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2019). Provably efficient reinforcement learning with linear function approximation

2019
[22]

Jin, Y., Yang, Z., and Wang, Z. (2021b). Is pessimism provably efficient for offline rl? In International Conference on Machine Learning , pages 5084--5096. PMLR

2021
[23]

Kakade, S. M. (2001). A natural policy gradient. In Dietterich, T., Becker, S., and Ghahramani, Z., editors, Advances in Neural Information Processing Systems , volume 14. MIT Press

2001
[24]

Y., and Mannor, S

Kumar, N., Agrawal, P., Ramponi, G., Levy, K. Y., and Mannor, S. (2024). Improved sample complexity for global convergence of actor-critic algorithms

2024
[25]

Lan, G. (2022). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes

2022
[26]

Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2024). Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics , 52(1):233--260

2024
[27]

Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2021). Softmax policy gradient methods can take exponential time to converge. In Conference on Learning Theory , pages 3107--3110. PMLR

2021
[28]

D., Chi, Y., and Chen, Y

Li, G., Zhan, W., Lee, J. D., Chi, Y., and Chen, Y. (2023). Reward-agnostic fine-tuning: Provable statistical benefits of hybrid reinforcement learning. arXiv preprint arXiv:2305.10282

2023 arXiv
[29]

P., Hunt, J

Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2019). Continuous control with deep reinforcement learning

2019
[30]

Liu, B., Cai, Q., Yang, Z., and Wang, Z. (2023a). Neural proximal/trust region policy optimization attains globally optimal policy

2023
[31]

Liu, Q., Weisz, G., György, A., Jin, C., and Szepesvári, C. (2023b). Optimistic natural policy gradient: a simple efficient policy optimization framework for online rl

2023
[32]

Mahankali, S., Hong, Z.-W., Sekhari, A., Rakhlin, A., and Agrawal, P. (2024). Random latent exploration for deep reinforcement learning

2024
[33]

N., Everitt, T., and Hutter, M

Martin, J., Sasikumar, S. N., Everitt, T., and Hutter, M. (2017). Count-based exploration in feature space for reinforcement learning

2017
[34]

Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2022). On the global convergence rates of softmax policy gradient methods

2022
[35]

P., Mirza, M., Graves, A., Lillicrap, T

Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T. P., Harley, T., Silver, D., and Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning

2016
[36]

and Szepesv \'a ri, C

Munos, R. and Szepesv \'a ri, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research , 9(27):815--857

2008
[37]

S., Ma, Y., Finn, C., Kumar, A., and Levine, S

Nakamoto, M., Zhai, Y., Singh, A., Mark, M. S., Ma, Y., Finn, C., Kumar, A., and Levine, S. (2023). Cal-ql: Calibrated offline rl pre-training for efficient online fine-tuning

2023
[38]

Neu, G., Jonsson, A., and Gómez, V. (2017). A unified view of entropy-regularized markov decision processes

2017
[39]

V., Russo, D., and Wen, Z

Osband, I., Roy, B. V., Russo, D., and Wen, Z. (2019). Deep exploration via randomized value functions

2019
[40]

F., Jiao, J., and Ramachandran, K

Rajaraman, N., Yang, L. F., Jiao, J., and Ramachandran, K. (2020). Toward the fundamental limits of imitation learning

2020
[41]

Rajeswaran, A., Kumar, V., Gupta, A., Vezzani, G., Schulman, J., Todorov, E., and Levine, S. (2017). Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint arXiv:1709.10087

2017 arXiv
[42]

Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2023). Bridging offline reinforcement learning and imitation learning: A tale of pessimism

2023
[43]

S., Bagnell, J

Ren, J., Swamy, G., Wu, Z. S., Bagnell, J. A., and Choudhury, S. (2024). Hybrid inverse reinforcement learning

2024
[44]

I., and Abbeel, P

Schulman, J., Levine, S., Moritz, P., Jordan, M. I., and Abbeel, P. (2017). Trust region policy optimization

2017
[45]

Sherman, U., Cohen, A., Koren, T., and Mansour, Y. (2024). Rate-optimal policy optimization for linear markov decision processes

2024
[46]

A., Krishnamurthy, A., and Sun, W

Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun, W. (2023). Hybrid rl: Using both offline and online data can make rl efficient

2023
[47]

Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction . The MIT Press, second edition

2018
[48]

Tan, K., Fan, W., and Wei, Y. (2024). Hybrid reinforcement learning breaks sample size barriers in linear mdps. In Advances in Neural Information Processing Systems

2024
[49]

and Xu, Z

Tan, K. and Xu, Z. (2024). A natural extension to online algorithms for hybrid RL with limited coverage. Reinforcement Learning Journal , 1

2024
[50]

van Hasselt, H., Guez, A., and Silver, D. (2015). Deep reinforcement learning with double q-learning

2015
[51]

and Pacchiano, A

Wagenmaker, A. and Pacchiano, A. (2023). Leveraging offline data in online reinforcement learning

2023
[52]

Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint , volume 48. Cambridge university press

2019
[53]

S., and Jiao, J

Wu, T., Yang, Y., Zhong, H., Wang, L., Du, S. S., and Jiao, J. (2022). Nearly optimal policy optimization with stable at any time guarantee

2022
[54]

Xiao, L. (2022). On the convergence rates of policy gradient methods

2022
[55]

J., Bai, Y., Jiang, N., and Kakade, S

Xie, T., Foster, D. J., Bai, Y., Jiang, N., and Kakade, S. M. (2022). The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04157

2022 arXiv
[56]

Xiong, N., Wang, Z., and Yang, Z. (2023). A general framework for sequential decision-making under adaptivity constraints

2023
[57]

S., Gower, R

Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., and Xiao, L. (2023). Linear convergence of natural policy gradient methods with log-linear policies

2023
[58]

Zanette, A., Cheng, C.-A., and Agarwal, A. (2021). Cautiously optimistic policy optimization and exploration with linear function approximation

2021
[59]

Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. D. (2022). Offline reinforcement learning with realizability and single-policy concentrability

2022
[60]

Zhao, H., He, J., and Gu, Q. (2023). A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation

2023
[61]

and Zhang, T

Zhong, H. and Zhang, T. (2023). A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes

2023
[62]

Zhou, Y., Sekhari, A., Song, Y., and Sun, W. (2023). Offline data enhanced on-policy policy gradient with provable guarantees

2023
[63]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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

[1] [1]

Abbasi-Yadkori, Y., Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C., and Weisz, G. (2019). POLITEX : Regret bounds for policy iteration using expert prediction. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 3692--3702. PMLR

work page 2019

[2] [2]

Agarwal, A., Henaff, M., Kakade, S., and Sun, W. (2020). Pc-pg: Policy cover directed exploration for provable policy gradient learning

work page 2020

[3] [3]

Agarwal, A., Jin, Y., and Zhang, T. (2022). Vo q l: Towards optimal regret in model-free rl with nonlinear function approximation

work page 2022

[4] [4]

M., Lee, J

Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research , 22(98):1--76

2021

[5] [5]

J., Jiang, N., Sekhari, A., and Xie, T

Amortila, P., Foster, D. J., Jiang, N., Sekhari, A., and Xie, T. (2024). Harnessing density ratios for online reinforcement learning

work page 2024

[6] [6]

and Russo, D

Bhandari, J. and Russo, D. (2022). Global optimality guarantees for policy gradient methods

work page 2022

[7] [7]

Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2024). Provably efficient exploration in policy optimization

work page 2024

[8] [8]

and Rosenberg, A

Cassel, A. and Rosenberg, A. (2024). Warm-up free policy optimization: Improved regret in linear markov decision processes

work page 2024