Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL

Bo Dai; Lin Xiao; Tong Yang; Yuejie Chi

REVIEW 2 major objections 6 minor 25 references

Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper claims that a single value-incentivized objective, optimized by an actor-critic update, achieves near-optimal regret in online reinforcement learning.

desk verdict A genuinely new single-objective optimistic actor-critic with a promising regret bound, but the proof of Theorem 1 has a repairable gap around Lemma 7 and the analyzed algorithm is an exact global oracle, not the practical first-order method. read the letter →

arxiv 2506.22401 v1 pith:TGLZL6AR submitted 2025-06-27 cs.LG math.OC

Tong Yang , Bo Dai , Lin Xiao , Yuejie Chi This is my paper

classification cs.LGmath.OC

keywords onlinereinforcementlearningexploration-exploitationtradeoffprimal-dualoptimizationactor-criticmethodsregretboundslinearMarkovdecisionprocessesoptimisticregularizationvalue-incentivizedexploration

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

This paper claims that the exploration–exploitation trade-off in online reinforcement learning can be cast as a primal–dual optimization problem, and that the resulting objective can be optimized by an actor-critic method with provable sample efficiency. The proposed value-incentivized actor-critic (VAC) method maximizes a single objective: the expected value of the current policy under the learned Q-function minus a regularization term that penalizes Bellman inconsistency with the data already collected. Under the linear MDP assumption, VAC is shown to suffer regret $O(dH^2\sqrt{T}\log T)$ in the finite-horizon setting, which is near-optimal up to a factor of $\sqrt{H}$, with an analogous guarantee in the infinite-horizon discounted setting. The argument extends to general function approximation under a low generalized Eluder coefficient condition, a measure of how well in-sample prediction errors control out-of-sample errors. A sympathetic reader would care because VAC avoids the bilevel optimization that makes earlier optimism-based methods hard to implement, while retaining a theoretical guarantee.

What carries the argument

The load-bearing object is a regularized Lagrangian for the constrained value maximization problem. Starting from maximizing $V_f^\pi(\rho)$ over $(f,\pi)$ subject to the Bellman consistency equation $Q_{f,h}(s,a)=r_h(s,a)+\mathbb{E}[Q_{f,h+1}(s',a')]$, the paper introduces dual variables $\lambda_h$ and a quadratic penalty $\beta\lambda_h^2/2$, then reparameterizes $\lambda_h=(Q_{f,h}-g_h)/\beta$. This converts the Lagrangian into $V_f^\pi(\rho)$ minus $(1/2\beta)$ times a squared Bellman residual difference, whose sample version is exactly the regularizer $L_t(f,\pi)$, and whose optimization over the helper function $g$ is absorbed into the loss. The same maneuver removes the max over actions that makes the earlier maximize-to-explore objective bilevel. The regret analysis then runs on three components: a covering argument with Freedman's inequality to control the Bellman residual martingale, a logarithmic policy-class error from the softmax policy class, and an elliptical-potential argument to control the value prediction error.

What would settle it

Run Algorithm 1 on a small linear MDP (for example $d=2$, $H=3$, with tabular feature maps) using a standard first-order optimizer for (17) and compare the empirical regret with the $\tilde{O}(dH^2\sqrt{T})$ bound; if the regret is linear in $T$, or if the per-episode objective gap $V_{\tilde{\pi}^\star}^{Q^\star}(\rho)-\alpha L_t(Q^\star,\tilde{\pi}^\star)-[V_{\pi_t}^{f_t}(\rho)-\alpha L_t(f_t,\pi_t)]$ is positive on any episode, then the exact-maximizer premise, and with it the transfer of Theorem 1 to the implemented algorithm, is violated.

Watch

Extended reading notes

Core claim

The paper's central claim is that optimism can be implemented as a value-incentive term rather than as an explicit bonus or confidence set. At each episode VAC solves $\max_{f\in\mathcal{Q},\pi\in\mathcal{P}}[V_f^\pi(\rho)-\alpha L_t(f,\pi)]$, where $V_f^\pi(\rho)$ is the expected value of policy $\pi$ under the Q-function $f$, and $L_t(f,\pi)$ is the squared Bellman consistency error of $f$ against the transition data collected so far, measured with the improvement that the best in-class function $g$ can achieve. Because the Bellman optimality equation is replaced by the Bellman consistency equation in the constraint, the objective is a single differentiable regularized Lagrangian instead of a bilevel program. The proof shows that under linear MDPs, where the optimal Q-function is realizable and the Bellman operator closes in the function class, the update's maximizer dominates the pair $(Q^\star,\tilde{\pi}^\star)$, and the regret decomposes into the value-incentive gap, the Bellman residual, and a policy-class model error of order $\log|\mathcal{A}|/B$. With the regularization coefficient $\alpha$ and policy temperature $B$ chosen as in the paper, this yields $\mathrm{Regret}(T)=O(dH^2\sqrt{T}\sqrt{\log(\log|\mathcal{A}|T/\delta)\log(1+T^{3/2}/d)})$ with probability at least $1-\delta$.

Load-bearing premise

The proof assumes that at every episode the nonconvex update (17) is solved exactly, returning the global maximizer of the value-incentivized objective; if a practical solver only finds an approximate stationary point, the key comparison inequality used to prove the regret bound can fail, and the regret guarantee no longer transfers.

Editorial extensions

If this is right

If the guarantee holds, VAC is a model-free online RL method with near-optimal regret that can in principle be trained with first-order updates, since both the value term and the Bellman residual are differentiable in the Q-function and the policy.
The discounted infinite-horizon version inherits the same structure, with sample complexity $\tilde{O}(d^2/((1-\gamma)^5\varepsilon^2))$ to reach an $\varepsilon$-optimal policy, so the single-objective design is not tied to the episodic horizon.
Under the generalized Eluder coefficient condition, the same algorithm achieves regret $\tilde{O}(H^{3/2}\sqrt{T})$ times a log-covering factor, extending the result to broader model classes such as linear mixture MDPs and low Bellman-Eluder-dimension models.
The policy-class model error $\log|\mathcal{A}|/B$ is controlled by choosing $B$ large, which means the log-linear policy class can approximate the optimal policy well enough that the value-incentive term drives exploration without an explicit exploration bonus.
The regret bound matches the minimax lower bound up to a $\sqrt{H}$ factor, so the price paid for the simple single-objective formulation is at most a mild horizon-dependent gap.

Reading between the lines

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

Editorial extension: the paper analyzes the exact global maximizer in (17), but a practical implementation replaces it with a first-order saddle-point update (critic evaluation then policy gradient); transferring the regret bound to that implementation would require showing the objective gap at each iterate is small, which the paper does not prove.
Editorial extension: the same primal-dual template could produce value-incentivized variants for other constrained RL formulations, such as safety-constrained or regularized objectives, by swapping the Bellman consistency constraint for the corresponding feasibility constraint and reusing the reparameterization.
Editorial extension: a direct falsifiable test of the mechanism is whether the objective gap $V_{\tilde{\pi}^\star}^{Q^\star}(\rho)-\alpha L_t(Q^\star,\tilde{\pi}^\star)-[V_{\pi_t}^{f_t}(\rho)-\alpha L_t(f_t,\pi_t)]$ stays nonnegative for the iterates produced by a first-order solver; if it goes positive, the regret bound in Theorem 1 no longer applies to the implemented algorithm.
Editorial extension: because the value-incentive term biases the critic toward optimistic Q-estimates, the method may combine with replay buffers or offline pre-training, but the current theory covers only the online interaction protocol.

Share X Bluesky LinkedIn Reddit HN

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

You should know two things about arXiv:2506.22401. VAC replaces the bilevel max over actions in MEX with a joint actor-critic objective that keeps the optimistic regularizer, and the paper backs it with a near-optimal regret bound in linear MDPs (and extensions). The primal-dual reading of MEX is a genuinely new way to see where the MEX regularizer comes from, and the VAC objective with Bellman consistency is not in Liu et al. 2024. The proofs are detailed and the regret decomposition (Lemmas 8 and 9) is internally coherent.

But there is a real proof gap in the write-up. Lemma 7 defines eπ* as a rho-argmax policy over the log-linear class and claims a pointwise bound V*_h(s) - V^{eπ*}_{f*,h}(s) ≤ log|A|/B for every s. The proof only establishes that bound for a pointwise-optimal policy, not for the rho-argmax. Lemma 8 Step 2 then uses the pointwise inequality on transitions into arbitrary next states. The stress-test counterexample (H=2, rho concentrated at s1, Q* supported at s2) shows the claimed inequality can fail badly. This is not a typo; it is load-bearing for Theorem 1. The good news: the fix is natural — choose the comparator as the pointwise softmax π̆_h ∝ exp(B Q*_{h+1}) instead of the rho-argmax, which lies in the policy class and satisfies both the rho-level and pointwise inequalities. With that change, the rest of the proof appears recoverable.

The second issue is the exact-oracle assumption. Algorithm 1's update (17) solves a nonconvex joint optimization exactly; the practical first-order version in Section 3.1 has no convergence or global-optimality guarantee, and no experiments. That is a real caveat but secondary — the theorem is about the oracle algorithm, and that is stated honestly.

So: the central idea is sound and the paper deserves a serious referee, but the version in front of you has a repairable gap in the proof of Theorem 1. If you are in the MEX/optimistic-regularization line, the primal-dual framing is worth your attention; just don't cite the regret theorem as is.

Referee Report

2 major / 6 minor

Summary. The paper proposes Value-Incentivized Actor-Critic (VAC), a method for online RL that maximizes a single objective combining a value bias with a squared Bellman-residual penalty, interpreted as the Lagrangian of a constrained value-maximization problem. Under linear MDP assumptions (Assumptions 1–3), the authors prove an episodic regret bound of O~(d H^2 sqrt(T)) (Theorem 1), a discounted infinite-horizon guarantee (Theorem 3), and an extension to general function approximation under a generalized Eluder coefficient assumption (Theorem 2). The main proof decomposes regret into a value-bias term and a value-estimation error term, bounding the former by the difference of regularized losses (Lemmas 7–8) and the latter by an elliptical-potential argument (Lemma 9).

Significance. If fully correct, the paper would provide a unified, non-bilevel objective for exploration in actor-critic RL with near-optimal regret under linear MDPs, and it gives a fresh primal-dual reading of the MEX objective. The decomposition in Lemmas 8 and 9 is coherent, the parameter balancing is explicit, and the extension to discounted MDPs and general function approximation broadens the scope. However, two load-bearing issues currently prevent the theorems from being accepted as stated: a genuine gap in Lemma 7 connecting the ρ-argmax policy to the pointwise value bound used subsequently, and an unstated global-optimization oracle assumption in Algorithms 1 and 2 that is not justified by the proposed first-order implementation. Both are repairable within the paper's framework, so the result is promising but not yet in publishable form.

major comments (2)

Lemma 7 is stated for eπ⋆_h := arg max_{π_h∈P_h} V^{π_h}_{f⋆,h}(ρ) (Eq. (27)), but the proof only establishes the pointwise gap for the softmax policy π_h(·|s) ∝ exp(B Q⋆_h(s,·)) (Eq. (39)). The passage from (43) to (28) is invalid: (43) gives max_{π'_h∈P_h} V^{π'_h}_{f⋆,h}(s) ≥ V⋆_h(s)−log|A|/B for every s, which does not control the ρ-argmax policy at states outside supp(ρ). The gap is load-bearing: Lemma 8 Step 2 uses (68), which requires V^{eπ⋆}_{f⋆,h+1}(s′) ≥ V⋆_{h+1}(s′)−log|A|/B for arbitrary next states s′. A concrete failure: take H=2, ρ=δ_{s1}, Q⋆_2(s1,a1)=1, Q⋆_2(s2,a2)=1 with one-hot features; the policy that is greedy at s1 but takes a1 at s2 is a ρ-argmax yet has value 0 at s2, contradicting (28) for B = T log2/(4H). The fix is to take the comparator to be the pointwise softmax policy \tildeπ_h(·|s) ∝ exp(B Q⋆_{h+1}(s,·)), which lies in P_h and satisfies both the inequality (30) (since V^{eπ⋆}_{f⋆}(ρ) ≥ V^{\tildeπ}_{f⋆}(ρ)) and the pointwise bound (68). The same repair is required for Lemma 10 (Appendix B.4) and Lemma 13 (Appendix C.2).
[Section 3.1 (Eq. (17)); proof of Theorem 1 (Eq. (30))] The regret theorems are proved for the exact global arg sup in Algorithm 1 (Eq. (17)) and Algorithm 2 (Eq. (159)). No oracle is stated as an assumption, and the objective V^π_f(ρ) − αL_t(f,π) is nonconvex in the policy parameters and nonconcave in the Q parameters; exact global maximization is not justified. The key inequality (30) requires (f_t,π_t) to be the exact maximizer at every round. The first-order actor-critic sketched in Section 3.1 (critic evaluation via (19) and policy gradient) is not analyzed for convergence or optimality, so the stated regret bound does not transfer to the practical scheme advertised in the contribution list. Either make the global-optimization oracle an explicit assumption and restrict the claims accordingly, or analyze the regret inflation caused by approximate maximization.

minor comments (6)

[Section 2, Eqs. (7) and (18)] The reward term is sometimes typeset as 'rh' instead of 'r_h'; please use consistent notation throughout.
[Appendix B.2.3, Eq. (48)] The proof uses the notation s′_{i,h+1} where the definition in (47) uses s_{t,h+1}; please unify the notation.
[Multiple equations (61), (74), (105), (186), (199)] 'Jenson's inequality' should be 'Jensen's inequality'.
[Algorithm 3] The algorithm lists an input 'player index n' that is never used; remove it or explain its role.
[Section 3.1, paragraph after Eq. (18)] The sentence 'and use the current policy π_t to collect new action a′ for each tuples' is grammatically broken and should be rewritten.
[Section 1.2, related work] The reference to 'Liu et al. [2020]' as a model-free variant of MEX appears to be a citation error; the MEX framework is introduced in Liu et al. [2024].

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret proof is self-contained and the overlapping-author citations are tool-level, not load-bearing.

full rationale

The paper's central claim is that Algorithm 1's objective, max_{f,pi} [V_f^pi(rho) - alpha L_t(f,pi)], attains near-optimal regret under linear MDP assumptions. The regret is an external performance measure, not a quantity that the algorithm maximizes by construction, so the claim is not self-definitional. The proof decomposes regret into a value-comparator term and a Bellman-error term, then bounds both with Freedman's inequality, covering-number arguments, and elliptical-potential lemmas that are written out in full in Appendix B. No fitted parameter is disguised as a prediction: the hyperparameters alpha and B are chosen from T, d, H, and log|A|, not fitted to data, and the theorem is a statistical guarantee rather than an empirical forecast. The overlapping-author citations are to Yang et al. (2025) for a covering-number technique and to Dai et al. (2018) for the dual-variable reparameterization; in both cases the relevant algebraic or probabilistic content is re-derived in the text (Eqs. (10)-(11) and Steps 1.1-1.3), so the citations are not load-bearing. The paper also reuses standard lemmas from Jin et al. (2020), Abbasi-Yadkori et al. (2011), and Du et al. (2021), which are external and machine-checkable. The exact-global-argsup oracle required in Eqs. (17) and (159) is an implementation/soundness gap, and the pointwise-gap issue in Lemma 7 is a proof-correctness concern, but neither reduces the theorem to its own inputs by construction. Therefore no circular step is exhibited.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard linear MDP and function approximation assumptions, plus two hand-chosen algorithm parameters alpha and B. No new physical or mathematical entities are postulated. The most consequential ledger item is the unstated exact global optimization oracle, which is not listed among Assumptions 1 through 10 but is required by the proofs.

free parameters (2)

alpha (regularization coefficient) = Eq. (21) for finite horizon; Eq. (160) for discounted
Regularization coefficient controlling exploration incentive. The theory selects it as a specific function of T, H, d, and delta; no data fitting, but the regret bound depends on this choice.
B (policy class radius coefficient) = B = T log|A|/(dH) in Theorem 1; B = T log|A|(1-gamma)/d in Theorem 3
Defines the width of the log-linear policy class. Chosen large enough so the model error log|A|/B is negligible in the regret bound. Not fitted to data, but a hand-set design parameter.

assumptions (5)

domain assumption Assumption 1 and Assumption 8: linear MDP with known feature map phi, unknown reward weight zeta, and unknown signed measures mu, with norm bounds.
Standard structural assumption enabling linear representation and Bellman completeness via Lemma 6. Invoked throughout Theorem 1 and Theorem 3.
domain assumption Assumption 3 and Assumption 10: log-linear softmax policy class with radius B H sqrt(d) (finite horizon) or B sqrt(d)/(1-gamma) (infinite horizon).
Used in Lemma 7 and Lemma 13 to bound the model error by log|A|/B. The radius B is chosen by the authors in the theorem statement, not independently known.
domain assumption Assumption 4: realizability, Bellman completeness, and boundedness of the Q-function class for general function approximation.
Needed for the general function approximation extension in Theorem 2; standard in prior MEX analysis and holds under linear MDP via Lemma 6.
domain assumption Assumption 6: low generalized Eluder coefficient (GEC).
Borrowed from Liu et al. (2024); controls out-of-sample prediction error in the general function approximation setting.
ad hoc to paper Exact global arg sup in Algorithm 1 Eq. (17) and Algorithm 2 Eq. (159) is achievable at every round.
The regret theorems are proven for the exact optimizer of a nonconvex objective; no oracle, convexity, or convergence analysis is provided. This is a load-bearing unstated premise.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL." pith.science (2026). https://pith.science/paper/TGLZL6AR

@misc{pith2026250622401,
  author       = {Pith},
  title        = {Pith review of: Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TGLZL6AR}},
  note         = {Machine review of arXiv:2506.22401}
}

read the original abstract

Online reinforcement learning (RL) with complex function approximations such as transformers and deep neural networks plays a significant role in the modern practice of artificial intelligence. Despite its popularity and importance, balancing the fundamental trade-off between exploration and exploitation remains a long-standing challenge; in particular, we are still in lack of efficient and practical schemes that are backed by theoretical performance guarantees. Motivated by recent developments in exploration via optimistic regularization, this paper provides an interpretation of the principle of optimism through the lens of primal-dual optimization. From this fresh perspective, we set forth a new value-incentivized actor-critic (VAC) method, which optimizes a single easy-to-optimize objective integrating exploration and exploitation -- it promotes state-action and policy estimates that are both consistent with collected data transitions and result in higher value functions. Theoretically, the proposed VAC method has near-optimal regret guarantees under linear Markov decision processes (MDPs) in both finite-horizon and infinite-horizon settings, which can be extended to the general function approximation setting under appropriate assumptions.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 8 canonical work pages

[1]

A policy π : S 7→∆(A) specifies an action selection rule, where π(a|s) specifies the probability of taking action a in state s for each (s, a) ∈ S × A

denotes the discount factor, P : S × A 7→ ∆(S) is the transition kernel, and r : S × A 7→[0, 1] is the reward function. A policy π : S 7→∆(A) specifies an action selection rule, where π(a|s) specifies the probability of taking action a in state s for each (s, a) ∈ S × A. For any given policy π, the value function, denoted by V π : S 7→R, is given as ∀s ∈ ...

work page 2014
[3]

(40) Here, H(·) is the entropy function satisfying 0 ⩽ H(p) ⩽ log |A|, ∀p ∈ ∆(A)

It follows that πh ∈ Ph, and for all s ∈ S, πh(·|s) is the solution to the following optimization problem [Beck, 2017, Example 3.71]: max p∈∆(A) ⟨p, Q⋆ h(s, a)⟩ + 1 B H (p) , where H(p) := − X a∈A p(a) logp(a). (40) Here, H(·) is the entropy function satisfying 0 ⩽ H(p) ⩽ log |A|, ∀p ∈ ∆(A). (41) The optimality of πh for (40), together with (41), implies ...

work page 2017
[5]

Kostrikov, O

I. Kostrikov, O. Nachum, and J. Tompson. Imitation learning via off-policy distribution matching. arXiv preprint arXiv:1912.05032,

arXiv 1912
[6]

Assumption 5 (Policy class)

Under Assumption 4, we set the policy class P as follows. Assumption 5 (Policy class). The policy class P = QH h=1 Ph is ∀h ∈ [H] : Ph := πh : πh(s, a) = exp (BQh(s, a))P a′∈A exp (BQh(s, a′)) , ∀Qh ∈ Qh (114) with some constant B >0. Moreover, drawing upon the work of Zhong et al. [2022], Liu et al. [2024], we require the MDP to feature a low generalized...

work page 2022
[10]

Gpt-4 technical report

OpenAI. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 ,

arXiv
[14]

G. Team, R. Anil, S. Borgeaud, J.-B. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al. Gemini: a family of highly capable multimodal models.arXiv preprint arXiv:2312.11805,

arXiv
[15]

M. Wang. Primal-dual π learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint arXiv:1710.06100 ,

arXiv
[16]

T. Xie, D. J. Foster, A. Krishnamurthy, C. Rosset, A. Awadallah, and A. Rakhlin. Exploratory pref- erence optimization: Harnessing implicit Q⋆-approximation for sample-efficient RLHF. arXiv preprint arXiv:2405.21046,

arXiv

Show all 25 references

[17]

T. Yang, B. Dai, L. Xiao, and Y. Chi. Incentivize without bonus: Provably efficient model-based online multi-agent RL for markov games. arXiv preprint arXiv:2502.09780 ,

arXiv
[18]

Zanette, D

A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for ran- domized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics , pages 1954–1964. PMLR,

1954
[19]

Zhang, D

S. Zhang, D. Yu, H. Sharma, H. Zhong, Z. Liu, Z. Yang, S. Wang, H. Hassan, and Z. Wang. Self-exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405.19332 ,

arXiv
[20]

Zhong, W

H. Zhong, W. Xiong, S. Zheng, L. Wang, Z. Wang, Z. Yang, and T. Zhang. GEC: A unified framework for interactive decision making in MDP, POMDP, and beyond. arXiv preprint arXiv:2211.01962 ,

arXiv
[21]

Lemma 1 (Freedman’s inequality, Lemma D.2 in Liu et al

13 A Technical Lemmas We provide some technical lemmas that will be used in our proofs. Lemma 1 (Freedman’s inequality, Lemma D.2 in Liu et al. [2024]). Let {Xt}t⩽T be a real-valued martingale difference sequence adapted to filtration {Ft}t⩽T . If |Xt| ⩽ R almost surely, then ...

2024
[23]

(113) This gives the desired result

Substituting (111) and (112) into (110) and reorganizing the terms, we have TX t=1 V πt ft (ρ) − V πt (ρ) ⩽ η TX t=1 t−1X i=1 HX h=1 E(si,ai)∼d πi ρ,h ℓh(ft, si, ai, πt) + (6H 2 + H/η)d(λ) + H 2λdT. (113) This gives the desired result. B.3 Extension to general function approxi...

2024
[1998]

K. Tan, W. Fan, and Y. Wei. Actor-critics can achieve optimal sample efficiency. arXiv preprint arXiv:2505.03710,

arXiv
[2014]

T. Ren, T. Zhang, L. Lee, J. E. Gonzalez, D. Schuurmans, and B. Dai. Spectral decomposition representation for reinforcement learning. arXiv preprint arXiv:2208.09515 ,

arXiv
[2015]

Moulin, G

A. Moulin, G. Neu, and L. Viano. Optimistically optimistic exploration for provably efficient infinite-horizon reinforcement and imitation learning. arXiv preprint arXiv:2502.13900 ,
[2017]

S. Cen, J. Mei, K. Goshvadi, H. Dai, T. Yang, S. Yang, D. Schuurmans, Y. Chi, and B. Dai. Value-incentivized preference optimization: A unified approach to online and offline RLHF. arXiv preprint arXiv:2405.19320,

arXiv
[2018]

Sikchi, Q

H. Sikchi, Q. Zheng, A. Zhang, and S. Niekum. Dual rl: Unification and new methods for reinforcement and imitation learning. arXiv preprint arXiv:2302.08560 ,

arXiv
[2020]

Nachum, Y

O. Nachum, Y. Chow, B. Dai, and L. Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in neural information processing systems , 32, 2019a. O. Nachum, B. Dai, I. Kostrikov, Y. Chow, L. Li, and D. Schuurmans. Algaedice: Policy...

1912 arXiv
[2021]

D. J. Foster, N. Golowich, and Y. Han. Tight guarantees for interactive decision making with the decision- estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory , pages 3969–4043. PMLR, 2023b. 10 D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q...

arXiv
[2022]

Foster, D

D. Foster, D. J. Foster, N. Golowich, and A. Rakhlin. On the complexity of multi-agent decision making: From learning in games to partial monitoring. InThe Thirty Sixth Annual Conference on Learning Theory, pages 2678–2792. PMLR, 2023a. D. J. Foster, S. M. Kakade, J. Qian, and...

arXiv
[2023]

Agrawal and R

S. Agrawal and R. Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprint arXiv:1705.07041,

arXiv
[2024]

R. Lu, G. Huang, and S. S. Du. On the power of multitask representation learning in linear mdp. arXiv preprint arXiv:2106.08053,

arXiv
[2025]

Nachum and B

O. Nachum and B. Dai. Reinforcement learning via fenchel-rockafellar duality. arXiv preprint arXiv:2001.01866,

2001 arXiv

Pith tools

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

[1] [1]

A policy π : S 7→∆(A) specifies an action selection rule, where π(a|s) specifies the probability of taking action a in state s for each (s, a) ∈ S × A

denotes the discount factor, P : S × A 7→ ∆(S) is the transition kernel, and r : S × A 7→[0, 1] is the reward function. A policy π : S 7→∆(A) specifies an action selection rule, where π(a|s) specifies the probability of taking action a in state s for each (s, a) ∈ S × A. For any given policy π, the value function, denoted by V π : S 7→R, is given as ∀s ∈ ...

work page 2014

[2] [3]

(40) Here, H(·) is the entropy function satisfying 0 ⩽ H(p) ⩽ log |A|, ∀p ∈ ∆(A)

It follows that πh ∈ Ph, and for all s ∈ S, πh(·|s) is the solution to the following optimization problem [Beck, 2017, Example 3.71]: max p∈∆(A) ⟨p, Q⋆ h(s, a)⟩ + 1 B H (p) , where H(p) := − X a∈A p(a) logp(a). (40) Here, H(·) is the entropy function satisfying 0 ⩽ H(p) ⩽ log |A|, ∀p ∈ ∆(A). (41) The optimality of πh for (40), together with (41), implies ...

work page 2017

[3] [5]

Kostrikov, O

I. Kostrikov, O. Nachum, and J. Tompson. Imitation learning via off-policy distribution matching. arXiv preprint arXiv:1912.05032,

arXiv 1912

[4] [6]

Assumption 5 (Policy class)

Under Assumption 4, we set the policy class P as follows. Assumption 5 (Policy class). The policy class P = QH h=1 Ph is ∀h ∈ [H] : Ph := πh : πh(s, a) = exp (BQh(s, a))P a′∈A exp (BQh(s, a′)) , ∀Qh ∈ Qh (114) with some constant B >0. Moreover, drawing upon the work of Zhong et al. [2022], Liu et al. [2024], we require the MDP to feature a low generalized...

work page 2022

[5] [10]

Gpt-4 technical report

OpenAI. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 ,

arXiv

[6] [14]

G. Team, R. Anil, S. Borgeaud, J.-B. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al. Gemini: a family of highly capable multimodal models.arXiv preprint arXiv:2312.11805,

arXiv

[7] [15]

M. Wang. Primal-dual π learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint arXiv:1710.06100 ,

arXiv

[8] [16]

T. Xie, D. J. Foster, A. Krishnamurthy, C. Rosset, A. Awadallah, and A. Rakhlin. Exploratory pref- erence optimization: Harnessing implicit Q⋆-approximation for sample-efficient RLHF. arXiv preprint arXiv:2405.21046,

arXiv