- 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 -function space, introducing the TQS algorithm. TQS selects a leader -function and samples challenger -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
-
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.
-
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
-
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 and the expected sample-complexity bound.
-
Which 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 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 -disagreement. However, recall that the disagreement is derived from the residual decomposition , by replacing 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.
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⋆ had a unit subgaussian variance proxy. We later relaxed, before submission, the boundedness to conditionally subgaussian rewards, and σ⋆2 now denotes a common conditional subgaussian variance proxy for Rt+γV⋆(St+1)−Q⋆(St,At). 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). The mixture supermartingale at Q⋆ is λd/2exp(St(Q⋆))/detΛt, so that Ville’s inequality gives the boundary βt(δ)=log(1/δ)+21log(detΛt/λd). As you observed, the unnormalized score printed in the submitted appendix would have required σ⋆2βt(δ). The complexity rate is Γ⋆=supω∈Ω(P)infQ∈B∫2σ⋆2eQ(s,a)2ω(ds,da), where B is the set of alternatives to the optimal policy. All along, Γ⋆ is the contraction exponent of the Gibbs law proportional to exp(−St)dΠ0, and the stopping time satisfies limsupδ↓0E[τδ]/log(1/δ)≤1/Γ⋆ 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 (Qt(s,a)−Qt(s,a))2/(2σ⋆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 Q, it holds that eQ=(Q⋆−Q)+γP(VQ−V⋆), and replacing Q⋆ 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)=(Qt−Qθ)(s,a)+ϕ(s,a)⊤Λt−1mt(θ^t)+γϕ(s,a)⊤Λt−1∑i<txi(Vθ−Vθ^t)(Si+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.