acceptodds
Under review as a conference paper at ICLR 2027

Deep Exploration as Sequential Testing in -Function Space

Abstract

Best-policy identification in Markov decision processes (MDPs) is fundamentally an information-acquisition problem: the learner must gather trajectories that resolve uncertainty about which sequences of actions are optimal. We formulate this objective as a sequential testing problem in the space of optimal -functions, where each policy induces a region of optimality and exploration seeks to identify the region containing the unknown Bellman fixed point. We introduce TQS, a model-free algorithm that implements this testing problem through a leader–challenger mechanism. At each round, TQS pairs an empirical estimate of with a challenger sampled from a Gibbs distribution based on empirical Bellman residuals, and uses the challenger's squared fitted Bellman residual as an adaptive exploration reward. Since this reward changes across rounds, TQS uses an online RL learner as a dedicated exploration controller, steering the agent toward trajectories that maximally separate the competing hypotheses. In linear MDPs, we show that TQS admits a saddle-point interpretation in which the behavior policy maximizes distinguishability against a randomized alternative, and we derive Gibbs-contraction and sample-complexity guarantees governed by an instance-dependent oracle rate. Unlike model-posterior methods, TQS operates directly in value-function space and extends naturally to neural function approximation. We instantiate a value-disagreement surrogate with Bayesian heuristics, and obtain strong results on large tabular and continuous state benchmarks.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, deep exploration, best-policy identification, pure exploration, sequential testing, posterior sampling, intrinsic rewards

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_1YRkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper frames best-policy identification in discounted infinite-horizon MDPs as sequential testing over the optimal QQ-function space, introducing the TQS algorithm. TQS selects a leader QQ-function and samples challenger QQ-functions using a Gibbs distribution driven by Bellman residuals. The theoretical contributions include an anytime certification statistic, an instance-dependent separation rate, Gibbs-contraction guarantees, and asymptotic expected sample-complexity bounds under linear-MDP. Experiments report improved performance over several RL baselines.

The contribution is promising, but the current inconsistencies prevent a reliable assessment of the theoretical guarantees and experimental validation.

Critical strengths
  1. A coherent connection between certification and exploration. Using alternatives that prevent certification to determine an exploration score gives a principled way to target decision-relevant uncertainty. The dedicated controller also addresses the need to navigate toward informative observations.

  2. An instance-dependent theoretical characterization. The analysis connects feasible state-action allocations, evidence accumulation, and Gibbs contraction to an asymptotic stopping-time bound. This provides a meaningful theoretical account of the exploration objective.

Critical weaknesses

The score normalization is inconsistent across the theoretical statements. Section 3.2 (line 260) defines

\lVert m_t(Q) \rVert_{\Lambda_t^{-1}}^2,$$ whereas Appendix A.1 (line 697) defines $$S_t(\theta)=\frac12 \lVert m_t(\theta) \rVert_{\Lambda_t^{-1}}^2.$$ Despite this change, Proposition 6 (line 738) retains the confidence boundary $$\beta_t(\delta) =\log(1/\delta)+\tfrac12\log\left( \frac{\det\Lambda_t}{\lambda^d}\right).$$ For the unnormalized score, this boundary should carry a factor of $\sigma_\star^2$, as indicated by the supermartingale in its proof. The normalization needs to be reconciled throughout the calibration, Gibbs-contraction, and sample-complexity arguments so that the claimed constants can be checked. **The paper gives different descriptions of the experimental exploration reward.** Section 5 states that the experiments use squared leader–challenger value disagreement (lines 439–440): $$\widehat r_t^{\mathrm{ex}}(s,a) =\frac{[\widehat Q_t(s,a)-\widetilde Q_t(s,a)]^2} {2\sigma_\star^2}.$$ However, Appendix D.1.4 specifies a squared fitted Bellman-residual reward (lines 2234–2235): $$\widehat r_t^{\mathrm{ex}}(s,a) =\tfrac12\operatorname{clip}_{[-E,E]} \big(\widehat g_{t,\widetilde Q_t}(s,a)\big)^2.$$ Section 5 acknowledges that value disagreement is a surrogate, but does not explain which parts of Appendix D apply to the experiments. This makes it difficult to connect the reported results to the algorithm analyzed theoretically.
Questions for authors
  1. Which score-normalization convention is intended? Please reconcile the definitions in lines 260 and 697 with the confidence boundary in Proposition 6, and clarify the corresponding normalization of Γ⋆\Gamma^\star and the expected sample-complexity bound.

  2. Which r^tex(s,a)\widehat r_t^{\mathrm{ex}}(s,a) produced Figure 1? Was it squared value disagreement from lines 439–440 or the fitted Bellman-residual reward from lines 2234–2235?

3 comments

Thank you for your careful reading and your positive comments. We appreciate that you found the connection between certification and exploration coherent, and that you valued the instance-dependent analysis linking feasible sampling allocations to evidence growth and the stopping time.

Our original analysis assumed bounded rewards, rescaled so that the Bellman residual at Q⋆Q^\star had a unit subgaussian variance proxy. We later relaxed, before submission, the boundedness to conditionally subgaussian rewards, and σ⋆2\sigma_\star^2 now denotes a common conditional subgaussian variance proxy for Rt+γV⋆(St+1)−Q⋆(St,At)R_t+\gamma V^\star(S_{t+1})-Q^\star(S_t,A_t). While we restored this factor in the main text, we inadvertently kept the unit-scale convention in parts of the appendix. We apologize for this inconsistency, which the revision corrects. The calibration, Gibbs-contraction and stopping arguments are unchanged once the score and the rate are expressed in the same units.

1. Which normalization enters Proposition 6 and the sample-complexity bound? Sections 3.2 and A.1 now both use St(Q)=∥mt(Q)∥Λt−12/(2σ⋆2)S_t(Q)=\lVert m_t(Q)\rVert_{\Lambda_t^{-1}}^2/(2\sigma_\star^2). The mixture supermartingale at Q⋆Q^\star is λd/2exp⁡(St(Q⋆))/det⁡Λt\lambda^{d/2}\exp(S_t(Q^\star))/\sqrt{\det\Lambda_t}, so that Ville’s inequality gives the boundary βt(δ)=log⁡(1/δ)+12log⁡(det⁡Λt/λd)\beta_t(\delta)=\log(1/\delta)+\tfrac12\log(\det\Lambda_t/\lambda^d). As you observed, the unnormalized score printed in the submitted appendix would have required σ⋆2βt(δ)\sigma_\star^2\beta_t(\delta). The complexity rate is Γ⋆=sup⁡ω∈Ω(P)inf⁡Q∈B∫eQ(s,a)22σ⋆2ω(ds,da)\Gamma^\star=\sup_{\omega\in\Omega(P)}\inf_{Q\in\mathcal B}\int \frac{e_Q(s,a)^2}{2\sigma_\star^2}\omega(ds,da), where B\mathcal B is the set of alternatives to the optimal policy. All along, Γ⋆\Gamma^\star is the contraction exponent of the Gibbs law proportional to exp⁡(−St)dΠ0\exp(-S_t)d\Pi_0, and the stopping time satisfies lim sup⁡δ↓0E[τδ]/log⁡(1/δ)≤1/Γ⋆\limsup_{\delta\downarrow0}\mathbb E[\tau_\delta]/\log(1/\delta)\le 1/\Gamma^\star under the assumptions of Theorem 4, which are now clearly stated at the begining of Section 4.

2. Which exploration reward produced Figure 1? On both DeepSea and Cartpole swingup, TQS used the squared leader-challenger disagreement (Q^t(s,a)−Q~t(s,a))2/(2σ⋆2)(\widehat Q_t(s,a)-\widetilde Q_t(s,a))^2/(2\sigma_\star^2) of Section 5, and not the clipped fitted residual of the initial appendix, which came from our earlier bounded-reward analysis. With neural networks, this reward is divided by a running estimate of its scale and clipped. Appendix D now states it clearly.

This reward stems from a decomposition of the Bellman residual. For any QQ, it holds that eQ=(Q⋆−Q)+γP(VQ−V⋆)e_Q=(Q^\star-Q)+\gamma P(V_Q-V^\star), and replacing Q⋆Q^\star by the leader and dropping the continuation term yields the disagreement. The fitted residual of the analysis satisfies the same decomposition exactly (Appendix D): e^t(Qθ;s,a)=(Q^t−Qθ)(s,a)+ϕ(s,a)⊤Λt−1mt(θ^t)+γϕ(s,a)⊤Λt−1∑i<txi(Vθ−Vθ^t)(Si+1).\hat e_t(Q_\theta;s,a)=(\widehat Q_t-Q_\theta)(s,a)+\phi(s,a)^\top\Lambda_t^{-1}m_t(\hat\theta_t)+\gamma\phi(s,a)^\top\Lambda_t^{-1}\sum_{i\lt t}x_i(V_\theta-V_{\hat\theta_t})(S_{i+1}). The second term is the fitted residual of the leader itself, which vanishes up to the ridge when the leader is a least-squares fixed point, as in the tabular case. The third term is the fitted difference of continuation values, which vanishes at pairs whose features are orthogonal to the data, such as unvisited pairs with one-hot features. Thus, the disagreement is the fitted residual without its continuation term, and the two coincide wherever no data are available yet.

To check that dropping this term does not drive the results, we also ran TQS with the fitted Bellman residual as the reward, keeping the leader, the challenger and the explorer fixed. On DeepSea, the two rewards give the same median number of episodes at every depth, so that the DeepSea results also hold for the reward of the analysis. With a neural leader and continuous actions, however, the fitted residual does worse on the two pendulum tasks. Indeed, the critic is then trained by temporal-difference updates and is not a least-squares fixed point, so that the second term of the decomposition dominates the reward. On Pendulum-v1, subtracting it recovers the result of the disagreement (Appendix D). Finally, the general response summarizes the other new experiments, including the comparison with DBMF-BPI.

Thank you for your response. The rebuttal addressed the 2 inconsistencies. However, the paper’s theoretical guarantee does not directly cover the squared leader-challenger disagreement used in Section 5. This remains a limitation of the experiment, and I, therefore, will keep the weak-reject score.

Thank you for your reply. We agree that the analysis covers the fitted Bellman residual, not the squared QQ-disagreement. However, recall that the disagreement is derived from the residual decomposition eQ=(Q⋆−Q)+γP(VQ−V⋆)e_Q=(Q^\star-Q)+\gamma P(V_Q-V^\star), by replacing Q⋆Q^\star with the leader and dropping the continuation term. Equivalently, it is the leading term of the leader-centered fitted residual, and the two coincide at unvisited pairs (Appendix D). To close the remaining gap on DeepSea, the revision runs TQS with the reward of the analysis, keeping the leader, the challenger and the explorer fixed: both rewards give the same number of episodes at every depth (100 runs per depth; Section 5 and Appendix D.5.3), so the DeepSea results also hold for the analyzed reward. With neural networks, the analysis does not apply to either reward, and the revision states this as a limitation.

Reviewer_JMKnOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates single-trajectory best-policy identification (BPI) in discounted MDPs as a sequential test over Q-functions. The authors propose TQS, an algorithm for testing in Q-function space, which samples challengers from a tempered Gibbs law over alternatives, and analyse a stopping rule based on a Bellman-residual moment. The theory covers finite linear MDPs with uniform mixing, a unique optimal policy and exact Gibbs sampling. With what Section 5 describes as a value-disagreement reward, TQS beats some competitors, including Bootstrapped DQN, DQN, PPO and RLSVI on DeepSea, and the first three on Cartpole swingup.

Critical strengths
  • A strenght of the paper is that it does not need to enumerate policies or a keep an uncertainty setover dynamics, and its testing side is clean.
  • The stopping rule is valid under the assumptions of realizability (optimal Q is linear in the features), bounded rewards and non-anticipating data collection. Termination and sample complexity guarantees require additional exploration assumptions.
  • The leader–challenger construction is a natural exploration technique for active sequential testing problems in bandits and MDPs (i.e., top-two sampling). The idea is that here we sample challenger Q-functions, weighted by their Bellman-residual scores, instead of challenger MDPs.
  • The DeepSea results look relatively good. At N=30N=30, the recommendation is first optimal on every reachable state after a median of about 10310^3 episodes, against just under 10410^4 for RLSVI and Bootstrapped DQN. About 95% of seeds succeed, against 70–75% (Fig. 1).
Critical weaknesses

I believe there are some critical weaknesses that affect the current state of the paper. Mainly that the rate can be far from optimal, the theory does not cover what was run, and the gains are not attributed to their source.

  • The rate Γ⋆\Gamma^\star that governs the sample complexity is optimal only for the paper's own test, and the paper never compares it with known instance-dependent rates.Particularly, it is never compared with the characteristic time T⋆T^\star of Al Marjani et al. (2021), nor even with its tractable convex relaxation U⋆U^\star . A comparison would clarify the statistical efficiency of the proposed test, and it would also be particularly important to relate Γ⋆\Gamma^\star to U⋆U^\star.

  • The theorems are proved for finite, uniformly mixing MDPs and an idealised algorithm, so they cover neither the setting nor the agents of the experiments. Section 2 allows "a measurable, possibly continuous state space" (line 157), but from App. B.1 on, the rate and sample-complexity proofs assume finite state and action spaces; Lemma 21, for instance, takes a union bound over states. Assumption A.1 further requires every stationary policy to be irreducible and to mix at a common geometric rate, which the explorer's analysis relies on. This is stronger than the communicating MDPs of earlier single-trajectory BPI work (Al Marjani et al., 2021). The guarantees are also only asymptotic; a non-asymptotic analysis, as recently done for NaS (Lazzaro et al., 2026, arXiv:2607.17201) which is based on the non-asymptotic analysis of Poiani et al. for TaS, would make the cost of navigation explicit.

  • The paper gives two incompatible exploration rewards for Fig. 1. Section 5 says "Our implementation uses a value-disagreement surrogate", namely (Q^t−Q~t)2/(2σ⋆2)(\hat Q_t-\tilde Q_t)^2/(2\sigma_\star^2). It is obtained by setting Yi(Q^t)≈0Y_i(\hat Q_t)\approx0, dropping the next-state correction γ(VQ−VQ^t)(si+1)\gamma(V_Q-V_{\hat Q_t})(s_{i+1}), and implicitly replacing the ridge fit by Q^t−Q\hat Q_t-Q (lines 436–439). App. D.1.4 and Algorithm 3, to which Section 5 defers, instead use the clipped fitted residual 12clip(g^t,Q~t)2\tfrac12\mathrm{clip}(\hat g_{t,\tilde Q_t})^2.

    Lines 131–133 call squared Q-disagreement a visit's contribution to the test. But if the leader and the challenger both satisfy the Bellman equation at (s,a)(s,a), a visit there adds nothing to the evidence rate of lines 366–367. The disagreement reward there is still γ2(P(VQ^t−VQ~t)(s,a))2/(2σ⋆2)\gamma^2\big(P(V_{\hat Q_t}-V_{\tilde Q_t})(s,a)\big)^2/(2\sigma_\star^2).

    I suspect this difference drives the DeepSea results, with one-hot features the fitted residual is zero at untried state-action pairs, while value disagrreement can remain positive there.

  • I find the experiments to not support the claims of the paper in a convincing way. They cannot attribute the gains to the testing-based exploration reward, sine all baselines try to maximize the value. Importantly, other pure-exploration baselines are missing, such as MDP-NaS in the tabular case, or more importantly DBMF-BPI (Russo & Proutiere, NeurIPS 2023), a deep model-free BPI method evaluated on DeepSea and Cartpole swingup. The only control is the greedy-challenger ablation.

Questions for authors
  1. How does 1/Γ⋆1/\Gamma^\star compare with the characteristic time T⋆T^\star of Al Marjani et al. (2021) ?
  2. Do the rate statements of Theorems 2–5 hold for continuous state spaces? If so, what replaces Lemma 21?
4 comments
AuthorsOpenReview ↗

Response 1/3

Thank you for your careful and expert reading. We appreciate your remarks on testing directly in QQ-function space, on the connection to top-two sampling, and on the DeepSea results. Your example of a state-action pair with positive value disagreement and zero Bellman residual pinpointed a claim that we needed to correct. We answer your two theoretical questions first, and then explain what the experiments measure.

1. How does 1/Γ⋆1/\Gamma^\star compare with the characteristic time? We agree that optimality within our own Gibbs construction leaves this question open, and the revision adds a two-sided comparison. Let TmbT_{\mathrm{mb}} denote the analogue of the navigation-constrained KL characteristic time of Al Marjani, Garivier and Proutière (2021) for our linear comparison class, in which rewards are Gaussian with common variance σR2\sigma_R^2 and conditionally independent of the successor state. Both information games optimize over the same feasible stationary occupations Ω(P)\Omega(P) and require optimality in every state. For 0<Γ⋆<∞0<\Gamma^\star<\infty, and under the assumptions of our exact stopping rule, we show that

\le \lim_{\delta\downarrow0} \frac{\mathbb E[\tau_\delta]}{\log(1/\delta)} =\frac{1}{\Gamma^\star} \le \frac{\sigma_\star^2}{\sigma_R^2} T_{\mathrm{mb}}.$$ The upper bound has a direct explanation: keeping $P$ fixed, the mean reward that makes a challenger $Q$ optimal is $r_Q=Q-\gamma PV_Q=r-e_Q$, and the one-step Gaussian KL to this alternative is exactly $e_Q^2/(2\sigma_R^2)$. For the lower bound, under any alternative model with optimal value $Q$, the Bellman residual of $Q$ has mean zero, whereas its mean under the true model is $e_Q$. By using the variational inequality for the KL and the common (Bellman) subgaussian-noise proxy $\sigma_\star^2$ lower-bound the one-step KL by $e_Q^2/(2\sigma_\star^2)$. For our bounded (expected) rewards case, the factor $\sigma_\star^2/\sigma_R^2$ can be bounded by $(1+\gamma v_{\max}/\sigma_R)^2$ (using Hoeffding), where $v_{\max}$ is the sup norm of the value functions in the class. However, when transitions are deterministic throughout the comparison class, we can take $\sigma_\star^2=\sigma_R^2$, and the two bounds coincide. Regarding $U^\star$, Al Marjani et al. derive a tractable upper bound on their KL characteristic time for tabular MDPs with rewards supported on $[0,1]$ (but do not bound the ratio to the optimal characteristic time). In contrast, our proposition compares directly with the KL benchmark on the Gaussian class. Since the admissible reward and alternatives differ, the two results do not give a direct ordering between $1/\Gamma^\star$ and their relaxation. [Al Marjani et al., Lemma 3 and Eq. (6)](https://proceedings.neurips.cc/paper_files/paper/2021/file/d9896106ca98d3d05b8cbdf4fd8b13a1-Paper.pdf) **2. Do Theorems 2-5 extend to continuous states, and what replaces Lemma 21?** Yes, under the revised assumptions, but with a restriction of scope that we state below. You correctly identified where the submitted proof used finiteness: Lemma 21 took a union bound over individual states to establish the stationary flow. The linear structure lets us prove a weaker statement that suffices. Indeed, for a fixed challenger, the evidence rate under an occupation $\omega$ depends on $\omega$ only through its feature covariance $\Sigma(\omega)$. The revised lemma (*Feasibility of empirical feature covariance limits*) shows that any subsequence of $G_T/(T-1)$ converges to some $\Sigma(\omega)$ for some feasible stationary occupation $\omega$. To prove it, we map each state to its vector of features over the finitely many actions, establish the flow identity on the compact closure of this feature space with a countable family of continuous test functions. The rate results still require bounded continuous features on a Borel state space, spanning, uniform fast mixing, and a positive action gap. We note that uniform mixing is stronger than the communicating assumption of MDP-NaS. These conditions also restrict what the extension covers, which the Discussion now states. Finally, the stopping time is $\delta$-correct for every $\delta$, while our comparison of expected stopping times gives the leading term as $\delta\downarrow0$, the explicit finite-confidence cost of navigation studied by Lazzaro et al. (2026) remains an interesting approach for future work. [Lazzaro et al.](https://arxiv.org/abs/2607.17201). In particular tight finite control of the mixing times of Proposition~10 would provide a deep understanding of the behavior of TQS for moderate budgets. This is now acknowledged in the conclusion
AuthorsOpenReview ↗

Response 2/3

3. Which reward was used, and what explains the empirical gains? Figure 1 used the squared leader–challenger disagreement and practical challenger proposals, whereas the rate proof uses the squared fitted conditional Bellman residual. Your example shows precisely how the two differ. For every pair, it holds that Q^−Q~=(eQ~−eQ^)+γP(VQ^−VQ~),\widehat Q-\widetilde Q=(e_{\widetilde Q}-e_{\widehat Q})+\gamma P(V_{\widehat Q}-V_{\widetilde Q}), which is the decomposition of Section 5 written with the leader in place of Q⋆Q^\star. The disagreement thus combines the local difference of Bellman residuals, which drives the evidence collected by a visit, and the discounted disagreement of the continuation values. In your example, only the second term remains.

We agree that lines 131–133 were imprecise: the disagreement at (s,a)(s,a) is not the evidence collected by a visit to (s,a)(s,a). However, the explorer does not act on the reward at a single pair. It is an average-reward learner, which maximizes the gain of its policy, that is, the average reward under the stationary occupation ω\omega of this policy, and the evidence rate is an average over the same occupations, ∫eQ~2dω/(2σ⋆2)\int e_{\widetilde Q}^2\mathrm d\omega/(2\sigma_\star^2). What matters is therefore which occupations each reward favors. The continuation term is nonzero only if the two hypotheses differ at pairs reachable from (s,a)(s,a): if their residuals coincide at every such pair, a contraction argument gives Q^=Q~\widehat Q=\widetilde Q there. Thus, the disagreement raises the gain of the occupations that lead to states where the hypotheses can be distinguished.

In your example, the fitted residual, with one-hot features and nn visits to (s,a)(s,a), the centered fit gives e^t(Q~t;s,a)≈λλ+n(Q^t−Q~t)(s,a)\hat e_t(\widetilde Q_t;s,a)\approx\frac{\lambda}{\lambda+n}(\widehat Q_t-\widetilde Q_t)(s,a), up to sampling noise: it equals the disagreement before the first visit, and decays to the residual of the challenger (which is zero in your example). With the fitted residual, the explorer thus reaches informative states through the gain alone, whereas the squared QQ-disagreement also rewards the pairs that lead to them.

Centering of the fit. For the submitted version, the ridge penalty of the fit was centered at zero: at a pair whose features are orthogonal to the data, the fitted residual is then zero, whereas the disagreement can remain positive. This remark led us to center the penalty at the leader–challenger difference in the revised definition of the fitted residual (Section 3.3): b^t(Qθ)=arg⁡min⁡b[∑i<t(Yi(Qθ)−xi⊤b)2+λ∥b−(θ^t−θ)∥22]=Λt−1[mt(Qθ)+λ(θ^t−θ)].\hat b_t(Q_\theta)=\arg\min_{b}\Big[\sum_{i\lt t}(Y_i(Q_\theta)-x_i^\top b)^2+\lambda\lVert b-(\widehat\theta_t-\theta)\rVert_2^2\Big]=\Lambda_t^{-1}\big[m_t(Q_\theta)+\lambda(\widehat\theta_t-\theta)\big]. Since Yi(Qθ)=Ri+γVθ(Si+1)−xi⊤θY_i(Q_\theta)=R_i+\gamma V_\theta(S_{i+1})-x_i^\top\theta, it holds that mt(Qθ)=mt(Q^t)+Gt(θ^t−θ)+γ∑i<txi(Vθ−Vθ^t)(Si+1)m_t(Q_\theta)=m_t(\widehat Q_t)+G_t(\widehat\theta_t-\theta)+\gamma\sum_{i\lt t}x_i(V_\theta-V_{\widehat\theta_t})(S_{i+1}), with Gt=∑i<txixi⊤G_t=\sum_{i\lt t}x_ix_i^\top, and Λt=λI+Gt\Lambda_t=\lambda I+G_t gives, for every (s,a)(s,a), e^t(Qθ;s,a)=(Q^t−Qθ)(s,a)+ϕ(s,a)⊤Λt−1mt(Q^t)+γϕ(s,a)⊤Λt−1∑i<txi(Vθ−Vθ^t)(Si+1).\hat e_t(Q_\theta;s,a)=(\widehat Q_t-Q_\theta)(s,a)+\phi(s,a)^\top\Lambda_t^{-1}m_t(\widehat Q_t)+\gamma\phi(s,a)^\top\Lambda_t^{-1}\sum_{i\lt t}x_i(V_\theta-V_{\widehat\theta_t})(S_{i+1}). The first term is the disagreement, and it appears without shrinkage precisely because the penalty is centered at θ^t−θ\widehat\theta_t-\theta: with a zero-centered penalty, it would be ϕ(s,a)⊤Λt−1Gt(θ^t−θ)\phi(s,a)^\top\Lambda_t^{-1}G_t(\widehat\theta_t-\theta), which vanishes at pairs orthogonal to the data. The second term is the fitted residual of the leader, which vanishes up to the ridge when the leader is a least-squares fixed point, as in the tabular case. The third term is the fitted continuation term, which vanishes at pairs orthogonal to the data. Hence, the disagreement is the fitted residual with its last two terms dropped, and the two rewards coincide at untried pairs.

Ablation: To check that the dropped terms do not drive the results, we ran TQS on DeepSea with the fitted residual as the reward, keeping the leader, the challenger and the explorer fixed. The two rewards give the same median number of episodes at every depth N=10N=10 to 3030. With a neural leader, however, the fitted residual does worse on the two pendulum tasks: the critic is trained by temporal-difference updates and is not a least-squares fixed point, so that the second term dominates the reward (Appendix D).

AuthorsOpenReview ↗

Response 3/3

We added DBMF-BPI (Russo and Proutière, 2023) on DeepSea and Cartpole swingup, with the authors' agent ported to JAX and checked against the original on copied weights (Appendix D.3). We also compared TQS with PIPS and the tabular MF-BPI on the MOCA instance of the PIPS experiments, which is particularly informative: a suboptimal action at the initial state gives direct access to a state where the optimal action still needs to be identified. All agents are compared on their recommendations, at equal numbers of transitions. DBMF-BPI · PIPS experiments

  • DeepSea, 100100 runs per depth (Appendix D.5.1): DBMF-BPI needs 2.42.4 to 3.23.2 times as many episodes as TQS to reach an optimal recommendation for N=10N=10 to 3030 (p<0.001p<0.001 at every depth), and ends the budget with an optimal recommendation on 9090 to 100100 runs, against all runs for TQS. Once it has found the reward, its behavior concentrates on the rewarding path: at N=12N=12, between episodes 200200 and 300300, it tries both actions in 7%7\% of the reachable cells, against 94%94\% for TQS. Hence, it does not resolve the action gaps off the path, and at N=22N=22, its recommendation is never optimal in every reachable cell, whereas those of TQS and RLSVI eventually are. The main criterion is now optimality from the initial state, and the every-cell criterion of the submitted figure illustrates this point. These runs replace those of the submission. Appendix D.5.4 also reports both agents on the original DeepSea configuration of Russo and Proutière.

  • Cartpole swingup, 100100 runs per height (Appendix D.5.2): The median final return of the recommendation of TQS is above the swingup threshold up to h=0.75h=0.75, and that of DBMF-BPI only up to h=0.5h=0.5 (p<0.001p<0.001 for h≤0.75h\le0.75). The recommendation of TQS eventually swings up at every evaluation on 9292 to 5858 runs for h≤0.75h\le0.75, against 7878 to 88 for DBMF-BPI. However, DBMF-BPI swings up for the first time sooner when h≤0.5h\le0.5, and no agent solves h=0.9h=0.9.

  • MOCA instance: With 66 states, TQS and PIPS identify the optimal policy on all runs within 2,0002{,}000 episodes, whereas the two configurations of MF-BPI do so on only 22%22\% and 10%10\% of the runs after 2,9002{,}900 episodes. From 33 to 77 states, TQS and PIPS reach 95%95\% of identified runs within a factor 1.51.5 of each other (360360 to 2,6002{,}600 and 320320 to 3,6803{,}680 transitions), while MF-BPI needs one to two orders of magnitude more, or does not get there within 10610^6 transitions (100100 runs for TQS, 3030 for PIPS, 2020 to 4040 for MF-BPI). The code is in the anonymous repository.

Two ablations keep the leader of TQS and change only how the data are collected (Appendix D.5.3). RLSVI recommends the same leader and draws noise of the same variance, but acts greedily on its draw: it needs 1.71.7 to 2.92.9 times as many episodes as TQS. Acting greedily on the challenger of TQS, without the explorer, reaches the reward on 9191, 2929 and 33 of 100100 runs at N=10N=10, 1414 and 1818, and on none beyond, as a uniformly random policy would. Therefore, the gains come mainly from the explorer, which plans over the disagreement, rather than from the draw itself.

Thank you for the detailed responses and for the revised paper. As today is the last discussion day and there's not much time to check the details, I acknowledge the changes, and I will consider them in more depth during the reviewer-AC discussion period.

Reviewer_swUrOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper studies best-policy identification in discounted MDPs by treating it as sequential testing in QQ-function space. The proposed TQS algorithm samples alternative QQ-functions that disagree with the current policy recommendation and uses their estimated Bellman residuals to guide a separate exploration policy. For linear MDPs, the authors derive an instance-dependent evidence rate and asymptotic guarantees for Gibbs contraction and expected sample complexity. The experiments on DeepSea and Cartpole swingup report improved sample efficiency over the tested baselines.

Critical strengths
  1. TQS performs policy-directed exploration directly in QQ-function space, without requiring posterior inference over transition dynamics. Using fitted Bellman residuals to guide exploration provides a natural connection between policy identification and model-free RL. The reported improvements on DeepSea and Cartpole swingup suggest that this approach can be effective in practice.
  2. The paper connects sequential testing based on Bellman residuals to an instance-dependent exploration rate. The max–min formulation accounts for both the difficulty of distinguishing alternative QQ-functions and the constraints on state–action visitation imposed by the MDP. This provides a useful theoretical characterization of the information that can be gathered for policy identification.
Critical weaknesses
  1. Section 3 defines StS_t with a factor of 1/σ⋆21/\sigma_\star^2, but Appendix A.1 leaves it out. With the appendix definition, Proposition 6 seems to need an extra σ⋆2\sigma_\star^2 factor in its confidence bound. Theorem 4 also gives 1/Γ⋆1/\Gamma^\star in its statement and σ⋆2/Γ⋆\sigma_\star^2/\Gamma^\star in the proof. The authors should check these definitions and constants.
  2. Theorem 2 relies on a leader that eventually identifies the optimal policy and an exploration learner with sublinear regret, but these requirements are not clearly stated with the theorem. Proposition 10 aims to provide such an explorer, yet its proof is only sketched. More details are needed for the replay evaluation with adaptive targets and the regret bound with changing rewards. The experiments also use approximate challenger sampling and a QQ-disagreement reward, so they do not directly test the algorithm covered by the theory.
Questions for authors
  1. Section 3 and Appendix A.1 use different definitions of StS_t. With the appendix definition, shouldn't the bound in Proposition 6 be St≤σ⋆2βtS_t\leq\sigma_\star^2\beta_t? Theorem 4 has a similar difference between its statement and proof, with 1/Γ⋆1/\Gamma^\star versus σ⋆2/Γ⋆\sigma_\star^2/\Gamma^\star. Which scaling is intended?
  2. Which leader and explorer does Theorem 2 cover? Algorithm 1 leaves both open, but the proof uses eventual correctness of the leader and sublinear regret of the explorer. I could not verify the replay-evaluation bound for adaptive targets from the proof sketch of Proposition 10. Could the authors provide more details on this step? Also, ηt=O(t−κ)\eta_t=O(t^{-\kappa}) does not imply log⁡T/ηT=o(T)\log T/\eta_T=o(T), as required in Appendix B.
  3. Section 5 gives two different descriptions of the "TQS, greedy challenger" ablation. One replaces the exploration controller with the challenger's greedy policy, while the other keeps the explorer and changes the challenger. Which version was used for Figure 1? I would also like to know whether the experiments used the QQ-disagreement reward in Section 5 or the fitted Bellman-residual reward in Appendix D, and how often the candidate sampler had to use a fallback.
5 comments
AuthorsOpenReview ↗

Response 1/3

Thank you for the careful review, for the close reading of the proofs, and the typos you detected, which we corrected in the revision. We also appreciate your positive comments on our work. We address each of your raised points below. The revision clarifies the normalization, the choice of the leader and the explorer, and the scope of the experimental results.

Normalization and scaling. In the manuscript, σ⋆2\sigma_\star^2 is a conditional subgaussian variance proxy for the centered Bellman residual at Q⋆Q^\star, namely Rt+γV⋆(St+1)−Q⋆(St,At)R_t+\gamma V^\star(S_{t+1})-Q^\star(S_t,A_t), conditionally on the current state-action pair. Our original proof assumed bounded rewards, rescaled so that σ⋆2=1\sigma_\star^2=1. When we extended the analysis to subgaussian rewards, we restored the explicit normalization in the main text, but inadvertently kept the unit-scale convention in parts of the appendix. We apologize for this inconsistency. The revision uses the same normalization throughout, and this correction leaves the concentration and evidence-growth arguments unchanged.

1. Proposition 6 and Theorem 4. You are correct that the unnormalized score of the submitted appendix requires the boundary σ⋆2βt(δ)\sigma_\star^2\beta_t(\delta). Our intended score is St(Q)=∥mt(Q)∥Λt−12/(2σ⋆2)S_t(Q)=\lVert m_t(Q)\rVert_{\Lambda_t^{-1}}^2/(2\sigma_\star^2), and with this definition, Proposition 6 gives St(Q⋆)≤βt(δ)S_t(Q^\star)\leq\beta_t(\delta) simultaneously for all tt, with probability at least 1−δ1-\delta. We use the same factor 1/(2σ⋆2)1/(2\sigma_\star^2) in the definition of the evidence rate Γ⋆\Gamma^\star, so that the leading constant of Theorem 4 is 1/Γ⋆1/\Gamma^\star. We removed the extra factor from its proof.

AuthorsOpenReview ↗

Response 2/3

2. The leader, the explorer, and the temperature schedule in Theorem 2.

  • Leader and recommendation: The natural leader is a minimum-score estimate, θ^t∈arg⁡min⁡θ∈ΘSt(Qθ)\hat\theta_t\in\arg\min_{\theta\in\Theta}S_t(Q_\theta), with recommendation π^t∈Greedy(Qθ^t)\hat\pi_t\in\mathrm{Greedy}(Q_{\hat\theta_t}), and we added a paragraph stating this explicitly (l. 270–278). This choice is closely related to fitted QQ-iteration (FQI): a linear FQI step regresses the targets Ri+γVθ(Si+1)R_i+\gamma V_\theta(S_{i+1}) on the features xix_i, and QθQ_\theta is a fixed point of this step exactly when the residual vanishes, that is, ∑i<txi(Ri+γVθ(Si+1)−xi⊤θ)=mt(Qθ)=0\sum_{i<t}x_i\bigl(R_i+\gamma V_\theta(S_{i+1})-x_i^\top\theta\bigr)=m_t(Q_\theta)=0. Therefore, any such fixed point in Θ\Theta has score zero, and in general, the minimum-score leader minimizes the Λt−1\Lambda_t^{-1}-norm of this residual. In practice, in particular in deep RL, the leader can be extracted from the collected data by an offline RL algorithm: on Cartpole swingup, both a CQL leader and an IQL leader worked well (Appendix D).

  • Explorer: We emphasize that, in practice, TQS is not tied to one explorer. The analysis uses two properties: (i) feature coverage, and (ii) sublinear regret against stationary comparators on the realized sequence of exploration rewards. Any online MDP learner with these properties can be used, and in our tests, MDPO, Politex and related methods gave comparable performance. The purpose of Proposition 10 is to provide a complete analysis for one such explorer, Replay Politex with a forced-action probability εt=t−k\varepsilon_t=t^{-k}, 0<k<10<k<1. The argument has three steps.

    1. Coverage: Under uniform mixing and the spanning condition, mixing in uniform actions with probability t−kt^{-k} gives λmin⁡(Gt)≥c⋅t1−k\lambda_{\min}(G_t)\geq c\cdot t^{1-k} with high probability, for any adaptive base policy, at the cost of only O(T1−k)O(T^{1-k}) forced actions.

    2. Estimation: Coverage and the uniform self-normalized bound make the fitted residuals uniformly accurate over Θ\Theta. Together with the positive action gap, they also imply that the leader eventually recommends π⋆\pi^\star, so that the alternative set is fixed on the late interval.

    3. Regret: The exponential-weights policy update controls the regret against each stationary comparator on the realized reward sequence. A separate argument, based on the Poisson equation and uniform mixing, controls the difference between stationary gains and the rewards collected along the trajectory. Regarding your concern about targets fitted on the same data, we expanded the replay-evaluation proof: we first prove concentration simultaneously over a deterministic cover of the possible target functions, and then apply this bound to the target selected from the replay.

Together, these steps give a regret of order O~(T(1+k)/2+T1−k+T1−κ)\widetilde O\bigl(T^{(1+k)/2}+T^{1-k}+T^{1-\kappa}\bigr). This is sufficient, since the evidence-growth theorem only requires the regret of the explorer and the estimation errors to be o(T)o(T).

Temperature: You are right that ηt=O(t−κ)\eta_t=O(t^{-\kappa}) alone is insufficient. We initially wrote O(t−κ)O(t^{-\kappa}), κ∈(0,1)\kappa\in(0,1), but meant Θ(t−κ)\Theta(t^{-\kappa}), that is, ηt=c⋅t−κ\eta_t=c\cdot t^{-\kappa} with c>0c>0, and we apologize for this confusing typo. The revision fixes c=1c=1 and takes ηt=t−κ\eta_t=t^{-\kappa}, which satisfies log⁡(T)/ηT=Tκlog⁡T=o(T)\log(T)/\eta_T=T^{\kappa}\log T=o(T) since 0<κ<10<\kappa<1.

AuthorsOpenReview ↗

Response 3/3

3. Figure 1, the exploration reward, and the fallback. The experiments used the squared leader–challenger disagreement and approximate challenger sampling, and thus evaluate a practical surrogate of the fitted Bellman-residual reward analyzed in Theorem 2.

  • Ablation: You are right that our two descriptions of the ablation conflicted. Moreover, the benchmark notebooks of the submission implemented a third variant, which acts greedily with respect to the leader and takes a random action with probability 0.050.05 on DeepSea and 0.010.01 on Cartpole swingup. Rather than reconcile them, we reran the ablation following the first description: the explorer is removed, and the data are collected by the greedy policy of the challenger, with the leader and the challenger law of TQS. On DeepSea, it reaches the reward on 9191, 2929 and 33 of 100100 runs at N=10N=10, 1414 and 1818, and none beyond. Indeed, the challenger perturbs each pair independently, so that its greedy policy picks either action with probability close to 1/21/2. In contrast, with the same challenger and the explorer, TQS succeeds on all runs at every depth.
  • Reward: Figure 1 used the disagreement of Section 5, not the clipped fitted residual of the submitted Appendix D.1.4, which came from our earlier bounded-reward analysis and is now removed. On DeepSea, the reward is exactly (Q^t−Q~t)2/(2σ⋆2)(\widehat Q_t-\widetilde Q_t)^2/(2\sigma_\star^2), while with neural networks, it is divided by a running estimate of its scale and clipped, as Appendix D now states. To connect the experiments with Theorem 2, we also ran TQS on DeepSea with the fitted Bellman residual as the reward, everything else being fixed: both rewards give the same median number of episodes at every depth (Mann–Whitney p≥0.3p\ge0.3, 100100 runs per depth). Moreover, on DeepSea, the challenger is an exact draw from the Gaussian law of the quadratic surrogate score restricted to the alternatives, since the sampler never falls back (see below).
  • Fallback: On DeepSea, at least one of the Kmax⁡=16K_{\max}=16 draws is an alternative in every round of every run, at every depth, and on Cartpole swingup, at least one of the Kmax⁡=8K_{\max}=8 candidates passes the check in every round. Hence, the fallback is never used on these two tasks, and it is used in at most 0.2%0.2\% of the rounds with continuous actions. On DeepSea, this is because the action gaps off the rewarding path, 0.01/N0.01/N, are far below the standard deviation of the draw, and the Gibbs law concentrates at rate Γ⋆\Gamma^\star, which is likely very low on DeepSea

The general response summarizes the other new experiments, including the comparison with DBMF-BPI, a related best-policy identification baseline.

We thank you again for the detailed review, which improved the paper. To summarize the contribution: to the best of our knowledge, TQS is the first best-policy identification algorithm derived from a sequential test in QQ-function space, in which the same score defines the stopping rule, the challenger distribution and the exploration reward. We analyze it for linear MDPs beyond finite state spaces, within the scope stated in the Discussion, and the analysis introduces tools that may be useful beyond this paper, including forced coverage with continuous features and the two-sided comparison between the model-free rate Γ⋆\Gamma^\star and the model-based characteristic time. In practice, beyond an estimate of Q⋆Q^\star for the leader, the algorithm needs only two components: a sampler of challenger QQ-functions and an online explorer with low regret. It can therefore be instantiated with neural value functions, and also with continuous actions, although the latter is outside our analysis. We are happy to discuss any remaining concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

General response

We thank the reviewers for their careful reading. The three reviews raise common points: the normalization of the score, the gap between the reward used in the experiments and the reward analyzed in the theory, and the absence of a dedicated best-policy identification (BPI) baseline. We revised the paper on each of these points. We summarize the changes below, and the individual responses give the details.

1. Normalization. The score is St(Q)=∥mt(Q)∥Λt−12/(2σ⋆2)S_t(Q)=\lVert m_t(Q)\rVert^2_{\Lambda_t^{-1}}/(2\sigma_\star^2) in Section 3 and in the appendix alike. Hence, the boundary βt(δ)\beta_t(\delta) of Proposition 6 does not have a σ⋆2\sigma_\star^2 factor. Moreover, Γ⋆\Gamma^\star uses the same normalization, so that the leading constant of Theorem 4 is 1/Γ⋆1/\Gamma^\star in both its statement and its proof.

2. Theory.

  • We add a two-sided comparison with the navigation-constrained characteristic time of Al Marjani et al. (2021): Tmb≤1/Γ⋆≤(σ⋆2/σR2)TmbT_{\mathrm{mb}}\le 1/\Gamma^\star\le(\sigma_\star^2/\sigma_R^2)T_{\mathrm{mb}}, with equality when transitions are deterministic across the class.
  • Theorem 2 now states the leader and the explorer it covers, and Proposition 10, which provides such an explorer (Replay Politex with forced exploration), now has a complete proof.
  • The Discussion states the limits of the analysis. First, it is asymptotic, and its bounds involve mixing times. Second, with continuous features, a unique optimal action at every state forces the optimal action to be constant on a connected state space, so that the theory mainly applies to discrete, possibly infinite, state spaces.

3. Experiments. Section 5 and Appendix D are rewritten from new runs, and the code is available at https://anonymous.4open.science/r/tqs-0E1F/.

  • Protocol: On DeepSea and Cartpole swingup, we use 100100 runs per agent and setting, and report medians with interquartile ranges. Section 5 and Appendix D describe what was run: the squared leader–challenger disagreement as the reward, Gaussian challengers kept only if they are alternatives, and no stopping rule.
  • New baseline: We add DBMF-BPI (Russo and Proutière, 2023), a model-free BPI method, on DeepSea and Cartpole swingup. We ported the authors' agent to JAX and checked the port against the original on copied weights.
  • Experiments on continuous actions (which our analysis does not cover): MountainCarContinuous, a pendulum swing-up and Pendulum-v1, with 5050 runs each.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.