Actor-Critics Can Achieve Optimal Sample Efficiency

We thank the reviewer for the comments and suggestions! We are glad that the reviewer thinks our study is well motivated and our paper is well written. We provide answers to the questions below. Please let us know if you have further questions or concerns!

Revisions

Moreover, we have revised our paper to mitigate the computational inefficiency issue by leveraging an offline dataset with good coverage to bypass the need for optimism, and included numerical experiments based on the suggestions from reviewer TW2G in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf).

Response to Weaknesses and Questions

Q1: It will be better if there is some discussion about lower bounds. Is there any lower bounds for the setting? How large is the gap if comparing the upper bounds in this paper to lower bounds?

Unfortunately, it does not seem like there exist lower bounds for general function approximation. This has impacted other works in a similar way, as for example both Agarwal et al. (2022) and Zhao et al. (2024) appeal to lower bounds for linear MDPs within their papers on online RL with general function approximation. The result of $\sqrt{T}$ regret is optimal in both papers, as well as ours, even though in the linear case our algorithms have a worse dependence on $H$ by a factor of $H^2$ (though this is not our focus – our focus is on the dependence on $T$). Achieving a rate that is minimax-optimal in the case of linear MDPs can be done via adapting the algorithm of Zhao et al. (2024) and making the necessary adjustments, though this is challenging and best left for future work.

Q2: The algorithm is not computationally efficient.

Thanks for raising this concern! We have managed to address this within the hybrid RL setting. More specifically, recent work (Song et al., 2023) shows that in hybrid RL settings with good offline coverage, optimism (which can often be computationally inefficient) isn’t necessary, and FQI is provably efficient. We extend this to the actor-critic setting with Algorithms 1H and 2H, corresponding to Algorithms 1 and 2 in our paper, but without computing confidence sets. When ERM is efficient, these become computationally practical. We show that:

• Algorithm 1H achieves a regret of

• Algorithm 2H achieves a regret of

where $c_{\text{off}}^*$ is the Bellman-type single-policy concentrability, $\beta^\pi$, and $\beta^*$ are confidence set widths scaling with the log-covering number, and $N_{\text{off}}$ is the number of offline samples. If $N_{\text{off}} = \Omega(T)$, we have $\sqrt{T}$ regret, and we incur only an additional factor of $\sqrt{c_{\text{off}}^*}$ as a price to pay for omitting optimism. This improves upon Zhou et al. (2023), who required $1/\epsilon^6$ samples.

Experimental results. (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf)

1. Optimism in linear MDPs. We compare Alg. 1 and Alg. 2 to a rare-switching version of LSVI-UCB on a linear MDP tetris task. The condition required for Alg. 1 to work holds here, as we do not clip the Q-function estimates. We see that Alg. 1 performs better than LSVI-UCB (!), and Alg. 2 achieves sqrt(T) regret even though it performs slightly worse than LSVI-UCB
2. Deep hybrid RL. We compare Algs. 1H & 2H (with offline pretraining) to Cal-QL (Nakamoto et al., 2023). Alg. 2H takes a max over 10 randomly sampled actions from the policy to enhance exploration as Cal-QL does (this can be viewed as a computationally efficient version of optimism, or alternatively as approximately targeting pi^*). It outperforms Cal-QL, which outperforms 1H. Neither uses pessimism. This supports the claim that hybrid RL can avoid both pessimism and full optimism while retaining strong performance.

We thank the reviewer for their comments. If you believe that the revisions we have made have improved the paper, we would greatly appreciate it if you decided to increase your score

1. Agarwal et al. (2022), VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation.
2. Zhao et al. (2024), A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation.
3. Song et al. (2023), Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient.
4. Nakamoto et al. (2023), Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning.

We thank the reviewer for helpful comments and suggestions on our paper! We also thank the reviewer for believing that our paper is well-structured and clearly presented, and note that we have provided detailed discussions in the appendix in addition to the main theorems. We have addressed your questions below. Please feel free to check and let us know for any additional questions!

Experiments

We have revised our paper and included numerical experiments based on the suggestions from reviewer TW2G in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf). Given the comments you’ve made on the effort to integrate theoretical analysis with experiments, we thought that you’d appreciate them. Here is a quick summary:

1. Optimism in linear MDPs. We compare Alg. 1 and Alg. 2 to a rare-switching version of LSVI-UCB on a linear MDP tetris task. The condition required for Alg. 1 to work holds here, as we do not clip the Q-function estimates. We see that Alg. 1 performs better than LSVI-UCB (!), and Alg. 2 achieves sqrt(T) regret even though it performs slightly worse than LSVI-UCB
2. Deep hybrid RL. We compare Algs. 1H & 2H (with offline pretraining) to Cal-QL (Nakamoto et al., 2023). Alg. 2H takes a max over 10 randomly sampled actions from the policy to enhance exploration as Cal-QL does (this can be viewed as a computationally efficient version of optimism, or alternatively as approximately targeting pi^*). It outperforms Cal-QL, which outperforms 1H. Neither uses pessimism. This supports the claim that hybrid RL can avoid both pessimism and full optimism while retaining strong performance.

Response to Weaknesses and Questions

Q1: One possible improvement would be to include discussions on lower bounds and provide more intuitive insights into the relationship between general function approximation and the linear case.

Thanks for raising this point! Lower bounds are sparse for classes with general function approximation. To illustrate, both Agarwal et al. (2022) and Zhao et al. (2024) appeal to lower bounds for linear MDPs within their papers on online RL with general function approximation. The result of $\sqrt{T}$ regret is optimal in both papers, as well as ours, even though in the linear case our algorithms have a worse dependence on $d$ and $H$ (though this is not our focus – our focus is on the dependence on $T$).

The linear MDP case is a special instance of general function approximation where the Q-functions are almost closed under truncated sums. This allows Sherman et al. (2024) and Cassel and Rosenberg (2024) to achieve $\sqrt{T}$ regret via bypassing the truncation and applying rare-switching to account for the bonus functions not being closed under truncated sums. We will include this discussion within the paper.

Q2: Additionally, it would be helpful to clarify the key differences or connections between actor-critic algorithms and general online RL algorithms. Actor-critic methods are a specific subset of online RL algorithms that separately learn a policy (the “actor”) and a value function (the “critic”) in real time. In contrast, general online RL encompasses any algorithm that updates its learning parameters from streaming experience. These can have actor components, critic components, both, or neither.

Other Remarks We also appreciate that the reviewer read Appendix E and found it to be helpful. We wanted to include it in the main paper, but had to omit it due to a lack of space. Given your comments, it seems like that was a short-sighted decision, and we’ll include it in the main paper within the revision.

If you believe that these revisions and changes have improved the paper, we would greatly appreciate it if you decided to increase your score

1. Agarwal et al. (2022), VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation.
2. Zhong and Zhang (2023), A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes
3. Zhao et al. (2024), A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
4. Sherman et al. (2024) Rate-Optimal Policy Optimization for Linear Markov Decision Processes
5. Cassel and Rosenberg (2024) Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes
6. Nakamoto et al. (2023), Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning.
7. Song et al. (2023), Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient.

We thank the reviewer for the helpful and insightful comments! We are glad you recognize our work as achieving \sqrt{T} regret for general function approximation under specific assumptions—extending beyond the linear setting considered in prior work. We’ve addressed your questions and incorporated suggestions into our revision.

Computational Efficiency and Numerical Experiments

We have also constructed computationally efficient versions of Algorithm 1 and 2 that require only an offline dataset with good coverage, and have also conducted a set of numerical experiments on the request of reviewer TW2G. The guarantees for Algorithm 1H and 2H, as well as the summary of the numerical experiments, can be found in our response to reviewer TW2G, and the results of the numerical experiments can be found in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf).

Response to Weaknesses and Questions

Weaknesses

1. W1: Assumption 3 – Dirac deltas as distributional candidates

Thanks for this thoughtful observation. The Bellman Eluder (BE) dimension was introduced by Jin et al. (2021), who primarily considered two types of distributions:

1. $\mathcal{D}_{\mathcal{F}}$: distributions induced by greedy policies $\pi^f$ , and
2. $\mathcal{D}_{\Delta}$: Dirac delta measures over state-action pairs.

They suggest an RL problem has low BE dimension if either variant is small. Our work aligns with this perspective:

• Alg. 1 does not require rare-switching and scales with the SEC, a more general and often weaker measure than BE dimension.
• Alg. 2 currently assumes low BE dimension under $\mathcal{D}_{\Delta}$, which is aligned with prior frameworks (e.g., Xiong et al., 2023). That said, this can be weakened to the $\ell_2$ eluder condition (Xiong et al., 2023) with nothing more than a change in notation. We present results in the BE framework for familiarity and generality (capturing linear MDPs, low-Eluder-dimension classes, etc.). We’ll clarify these distinctions in the revision, and are happy to make the generalization to the $\ell_2$ eluder condition.

2. W2: Generalizability of regret bounds

We appreciate this concern. While SEC can depend on T , it typically scales better than the BE dimension and is more general. Importantly, BE dimension is known to scale as \sqrt{T} at worst (not linearly), so the regret result for Alg. 1 remains meaningful. Though Alg. 2 assumes low BE dimension under \mathcal{D}_{\Delta}, this can be relaxed to the \ell_2 eluder condition with minimal modification. This class includes:

1. tabular and linear MDPs
2. low Eluder dimension classes
3. linear mixture MDPs
4. kernelized nonlinear regulators
5. the SAIL condition
6. undercomplete POMDPs In all these settings, Alg. 2 achieves $\sqrt{T}$ regret.

Methods

1. M1: Policy not derived from the current function This is mostly a notational choice for cleaner proofs. As in GOLF (Xie et al., 2022), the critic is chosen from the prior confidence set; in other works (e.g., Zhong & Zhang, 2023), the actor update is based on the current critic. We follow these conventions for simplicity, though users need not in practice.

Questions

1. Q1: Assumptions on state and action spaces There are no specific assumptions here—the state and action spaces can be continuous or large. General function approximation accommodates this flexibility.

2. Q2: Superscript (t) in Equation 1 Thanks for catching this! The summation should read $(s, a, r, s{\prime}) \in \mathcal{D}_h^{(t)}$, not $\mathcal{D}$. We’ll fix this in the revision.

3. Q3: Definition 1 – Bellman error and auxiliary function class Yes—the Bellman error $f_h - \mathcal{T} f_{h+1}$ , with $f \in \mathcal{F}$, belongs to the auxiliary class $\mathcal{G}$. We’ll clarify this in the text.

4. Q4: Covering number notation in Theorem 1 The term $\mathcal{N}_{\mathcal{F}, (T^{\Pi})^{T} \mathcal{F}}$ represents the covering number of the union of two function classes: $\mathcal{F}$ and $(T^{\Pi})^T \mathcal{F}$ . We agree this should be stated more clearly and will revise accordingly.

We also thank the reviewer for the very thorough list of errata you have provided within your remarks on clarity, and will make the revisions requested. Let us know if further clarification is needed—we sincerely appreciate your thoughtful review! If our responses have successfully addressed your concerns, we would be sincerely grateful if you considered adjusting your score.

1. Xiong et al. (2023), A General Framework for Sequential Decision-Making under Adaptivity Constraints.
2. Jin et al. (2021), Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms.
3. Zhong and Zhang (2023), A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes.

We thank the reviewer for providing helpful comments and suggestions to our paper! We are glad that the reviewer believes our theoretical justification to be well-supported. We have revised our paper and included numerical experiments based on the suggestions from the reviewer in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf).

Comments Regarding Corollary 2: $\text{OPT}^*, \text{OPT}^f$ are not formal definitions, but placeholders for user-defined bounds on error terms for their chosen optimizer. We’ll clarify this in the revision.

Response to Weaknesses and Questions

W1: Lack of experiments and computational inefficiency. These are very valid concerns. We address them below.

Computational inefficiency. Optimism is a powerful yet computationally expensive approach in RL. Recent work (Song et al., 2023) shows that in hybrid RL settings with good offline coverage, optimism isn’t necessary, and FQI suffices for provable efficiency. We extend this to the actor-critic setting with Algorithms 1H and 2H, corresponding to Algorithms 1 and 2 in our paper, but without computing confidence sets. When ERM is efficient, these become computationally practical. We show that:

• Algorithm 1H achieves a regret of

• Algorithm 2H achieves a regret of

where $c_{\text{off}}^*$ is the Bellman-type single-policy concentrability, $\beta^\pi$, and $\beta^*$ are confidence set widths scaling with the log-covering number, and $N_{\text{off}}$ is the number of offline samples. If $N_{\text{off}} = \Omega(T)$, we have $\sqrt{T}$ regret, and we incur only an additional factor of $\sqrt{c_{\text{off}}^*}$ as a price to pay for omitting optimism. This improves upon Zhou et al. (2023), who required $1/\epsilon^6$ samples.

Experimental results.

1. Optimism in linear MDPs. We compare Alg. 1 and Alg. 2 to a rare-switching version of LSVI-UCB on a linear MDP tetris task. The condition required for Alg. 1 to work holds here, as we do not clip the Q-function estimates. We see that Alg. 1 performs better than LSVI-UCB (!), and Alg. 2 achieves sqrt(T) regret even though it performs slightly worse than LSVI-UCB
2. Deep hybrid RL. We compare Algs. 1H & 2H (with offline pretraining) to Cal-QL (Nakamoto et al., 2023). Alg. 2H takes a max over 10 randomly sampled actions from the policy to enhance exploration as Cal-QL does (this can be viewed as a computationally efficient version of optimism, or alternatively as approximately targeting pi^*). It outperforms Cal-QL, which outperforms 1H. Neither uses pessimism. This supports the claim that hybrid RL can avoid both pessimism and full optimism while retaining strong performance.

Note: In the plots, the first 1000 evaluation steps correspond to offline pretraining. Alg. 1H and 2H naturally underperform initially before fine-tuning begins. All plots are smoothed following WandB defaults.

We hope that these experiments address your concerns regarding real-world feasibility.

Q2: Why does the regret bound for Algorithm 2 still include the SEC term, despite assuming a bounded Bellman-Eluder (BE) dimension?

We thank the reviewer for this remark, which allows us to realize a subtlety. We use SEC over BE because it is generally tighter. However, Xie et al. (2022, Prop. 14) show that SEC is upper bounded by BE under the greedy policy’s occupancy measure, but not the BE dimension for Dirac deltas (Jin et al., 2021, App. H). Still, we can use Xiong et al. (2023, Eqs. G.13–G.14) to bound the term containing the SEC with the Bellman eluder dimension for Dirac deltas. We’re happy to clarify or include this in the revision.

Q3: Can the number of critic updates be bounded more tightly when updates are small?

Yes – thank you for this insightful question. One can use an $\epsilon$-net and collapse nearby critics when $\exp(\eta(f - f’)) < \epsilon/2$, which can reduce the bound significantly. This is a great observation that we would be more than happy to include in the paper.

Q4: When is Algorithm 1 preferable to Algorithm 2?

Though Alg. 2 often performs better, it may underperform when the Q-function sum has a low-dimensional structure (e.g., linear MDP Tetris). This is due to policy resets during rare-switching critic updates, which disrupt learning. Also, as shown in Table 1, Alg. 2 incurs an extra $dH$ factor in settings favorable to Alg. 1.

We truly appreciate the reviewer’s helpful and encouraging comments. If our revisions address your concerns, we’d be grateful if you would consider raising your score.