REVIEW 3 major objections 5 minor 1 cited by
Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read The optimal way to collect data for multi-policy, multi-reward evaluation is to sample in proportion to a one-step value-deviation measure, and MR-NaS provably achieves this rate up to a constant.
desk verdict A real contribution to multi-policy evaluation, but the headline optimality claim rests on an unproven constant-factor gap between the relaxed and exact characteristic times. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the one-step value deviation $\rho^\pi_r(s,s') := V^\pi_r(s') - \mathbb{E}_{\hat{s}\sim P(s,\pi(s))}[V^\pi_r(\hat{s})]$, which measures how much the value of policy $\pi$ under reward $r$ at a next state $s'$ deviates from its expected value after taking $\pi$'s action in $s$. A state with large $\|\rho^\pi_r(s)\|_\infty$ is 'confusing': a statistically near-invisible perturbation of the transition function can change the value by more than $2\epsilon$, and these alternative models are exactly what the lower bound must rule out. The relaxed characteristic time $U_\epsilon(\omega;M) = \sup_{\pi\in\Pi, r\in R_\pi}\max_s \gamma^2\|\rho^\pi_r(s)\|_\infty^2 / (2\epsilon^2(1-\gamma)^2\omega(s,\pi(s)))$ packages the deviations into a convex program whose minimizer $\omega^\star$ is the optimal data-collection distribution. Writing $\rho^\pi_r(s,s') = e_{s'}^\top\Gamma^\pi(s)r$ with $\Gamma^\pi(s) = (I - \mathbf{1}P(s,\pi(s))^\top)(I-\gamma P^\pi)^{-1}$ turns the maximization over rewards into linear or convex programs, with a closed form over the full reward cube $[0,1]^S$. The machinery converts an abstract infimum over confusing models into a concrete proportional-sampling rule.
What would settle it
Take any small tabular MDP (for instance the two-state example the paper uses to show non-convexity), fix $\epsilon$ and a target policy–reward pair, compute the true characteristic time $T^\star_\epsilon(M)$ by brute-force enumeration over all alternative transition functions that change the value by more than $2\epsilon$, and compare it with the relaxed rate $U^\star_\epsilon(M)$ from Theorem 4.7; if the ratio $U^\star_\epsilon/T^\star_\epsilon$ diverges or grows steeply as $\epsilon \to 0$ or as the transition probabilities vary, the constant-factor optimality claim fails. Running MR-NaS in the same MDP and measuring $\mathbb{E}[\tau]/\log(1/\delta)$ against both quantities would show which rate the algorithm actually tracks.
Extended reading notes
Core claim
The paper's central claim is that the sample complexity of online $(\epsilon,\delta)$-PAC policy evaluation over multiple policies and reward sets is governed by a single instance-dependent quantity — the relaxed characteristic time $U^\star_\epsilon(M)$ — and that the exploration rule it induces is asymptotically optimal up to a constant factor, a claim the paper states as the first instance-specific lower bound for this setting. The carrier of the argument is the one-step value deviation $\rho^\pi_r(s,s') = V^\pi_r(s') - \mathbb{E}_{\hat{s}\sim P(s,\pi(s))}[V^\pi_r(\hat{s})]$, a variance-like measure of how much the value of policy $\pi$ under reward $r$ spreads from the expected next-state value; the optimal allocation samples each state–action pair in proportion to $\gamma^2\|\rho^\pi_r(s)\|_\infty^2 / (2\epsilon^2(1-\gamma)^2)$, evaluated at the worst-case policy–reward pair. The paper proves a lower bound of $T^\star_\epsilon(M)$ (Theorem 4.4), a convex relaxation $U_\epsilon(\omega;M)$ of the potentially non-convex characteristic time that makes the optimal allocation computable for finite and convex reward sets (Theorem 4.7), and a closed-form allocation for the reward-free case computed from the discounted fundamental matrix (Corollary 4.8). For the MR-NaS algorithm — certainty-equivalence planning into the relaxed rate, mixed with a forcing policy, plus a stopping rule — it proves that the returned values are $\epsilon$-accurate for every policy and reward with probability at least $1-\delta$, that the algorithm stops almost surely, and that $\limsup_{\delta\to 0} \mathbb{E}[\tau]/\log(1/\delta) \le 4U^\star_\epsilon(M)$.
Load-bearing premise
The load-bearing premise is that the relaxed characteristic time $U_\epsilon$, in which the algorithm's upper bound is stated, is within a constant factor of the true characteristic time $T_\epsilon$, in which the lower bound is stated; Section 4.3 explicitly leaves the gap $|U_\epsilon - T_\epsilon|$ unquantified and says quantifying it is future work, so if the ratio $U^\star_\epsilon/T^\star_\epsilon$ is unbounded or large, the claim of optimality up to a constant factor fails.
Editorial extensions
If this is right
- MR-NaS attains the $(\epsilon,\delta)$-PAC guarantee with $\mathbb{E}[\tau] \le 4U^\star_\epsilon(M)\log(1/\delta)$ asymptotically, matching the instance-specific lower bound up to a constant factor.
- The optimal exploration rule is concrete: sample each state–action pair $(s,\pi(s))$ in proportion to the squared one-step value deviation $\|\rho^\pi_r(s)\|_\infty^2$ of the hardest policy–reward pair, a quantity computable from value estimates and the transition model.
- Sample complexity scales with the worst-case policy–reward pair rather than their sum, so adding policies or rewards to the evaluation set does not compound the data requirement.
- For reward-free evaluation over all rewards $[0,1]^S$, the optimal allocation has a closed form in terms of the discounted fundamental matrix $\Gamma^\pi(s)$, so no reward-side optimization is needed.
- Any behavior policy that renders a high-deviation state transient is provably suboptimal — its information rate collapses to zero — so persistent coverage of high-deviation states is necessary for optimal exploration.
Reading between the lines
- A direct numerical check, not performed in the paper, would settle the strength of the optimality claim: compute $U^\star_\epsilon/T^\star_\epsilon$ by exhaustive enumeration on small MDPs (such as the two-state example in the paper) and see whether the unquantified gap stays bounded as $\epsilon\to 0$.
- The proportional-to-deviation allocation is the PAC analogue of variance-optimal importance sampling; one would expect the same sampling rule to improve finite-sample off-policy evaluation and to extend to stochastic target policies and function approximation, settings this paper does not treat.
- A cheap testable signature of the theory is that visit counts under MR-NaS in a fixed tabular environment should grow roughly in proportion to $\|\rho^\pi_r(s)\|_\infty^2 / U^\star_\epsilon(M)$ over long runs; the paper reports estimation error but not the realized allocation, so this comparison is open.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online (epsilon, delta)-PAC policy evaluation in discounted tabular MDPs when multiple policies must be evaluated over multiple reward sets, with a value-vector error criterion. It first derives an instance-specific lower bound on the sample complexity (Theorem 4.4) expressed through a characteristic time T*_epsilon, defined via an optimization over confusing alternative models. Because this optimization is non-convex (illustrated by Example 4.6), the paper introduces a convex relaxation U_epsilon(omega; M) (Theorem 4.7), and shows how to compute the relaxed optimal allocation for finite and convex reward sets, including a closed form for the reward-free case (Corollary 4.8). The algorithm MR-NaS, adapted from the authors' prior multi-reward best-policy-identification work, is then analyzed: Theorem 5.2 states that MR-NaS is (epsilon, delta)-PAC, stops almost surely, and satisfies limsup E[tau]/log(1/delta) <= 4 U*_epsilon(M). The paper claims in Sections 1 and 7 that this constitutes asymptotic optimality up to a constant factor. Experiments on four tabular environments compare MR-NaS with SF-NR, GVFExplorer, and noisy-policy baselines.
Significance. If the constant-factor optimality claim were fully established, this would be a notable contribution: it would give the first instance-dependent lower bound for multi-reward multi-policy evaluation and a practical algorithm matching it up to a constant. The paper's machinery is substantial: the lower bound construction via confusing models, the relaxation in terms of the one-step value deviation rho, the closed-form solution for reward-free evaluation, and the extension of MR-NaS all appear technically coherent, and the appendix contains detailed proofs. The code is provided, which supports reproducibility. The main reservation is that the headline guarantee is not supported by the stated theorems: Theorem 5.2 bounds the algorithm by the relaxed rate U*, while the lower bound is the exact rate T*, and the paper explicitly leaves the gap U*/T* to future work. The experimental results show good empirical accuracy of MR-NaS relative to baselines, but they do not validate the asymptotic constant-factor claim.
major comments (3)
- [Section 4.3, Eq. (6); Theorem 5.2; Section 1] The advertised claim of 'asymptotic optimality for policy evaluation up to a constant factor' is not established by the stated results. Theorem 5.2 gives limsup_{delta->0} E[tau]/log(1/delta) <= 4 U*_epsilon(M), while the lower bound of Theorem 4.4 is liminf >= T*_epsilon(M). For the optimality claim to hold, one needs U*_epsilon(M) <= C T*_epsilon(M) for a constant C independent of epsilon, delta, gamma, and the MDP. Section 4.3 explicitly states that 'quantifying the gap |U_epsilon(omega; M) - T_epsilon(omega; M)| remains challenging, and we leave this analysis to future work', and Section 4.1 only reports a belief that the looseness is at most a constant factor. Without a proof of the constant-factor gap, Theorem 5.2 only shows that MR-NaS attains the relaxed rate, not that the relaxed rate is within a constant of the true optimal rate. This is a load-bearing gap in the central claim of the paper.
- [Theorem 4.7; Example 4.6; Eq. (2)] The relaxation in Theorem 4.7 is not a provably tight surrogate for the true characteristic time. The true rate T_epsilon(omega; M) in Eq. (2) involves an infimum over confusing models in Alt^epsilon_pi,r(M) with rewards restricted to R^epsilon_pi, whereas the relaxed rate U_epsilon in Eq. (6) replaces this by a supremum over the full reward set R_pi and bounds the KL terms using a one-sided necessary condition on the value deviation rho. Example 4.6 shows that the set of confusing parameters can be non-convex, so this is not a benign substitution. Theorem 4.7 provides only T <= U; it gives no quantitative comparison between U*_epsilon and T*_epsilon. Given that Section 4.3 leaves the gap analysis to future work, the paper must either prove the needed bound under its stated assumptions (or a clearly specified subclass, such as reward-free evaluation with the canonical basis, where Corollary 4.8 may make the analysis tractable), or reframe the optimality claim as a conjecture and present Theorem 5.2 as a guarantee relative to the relaxed quantity only.
- [Section 4.1 and Section 5; Theorem 5.2] The use of the 2epsilon separation also introduces an unquantified constant relative to any 'exact' lower bound for epsilon-accurate evaluation. The text says the 2epsilon weakening 'potentially weakens the resulting lower bound' and states 'we believe the looseness is at most a constant factor (see Theorem 5.2)', but Theorem 5.2 does not connect T*_epsilon (defined with 2epsilon separation) to a rate for algorithms that only need epsilon separation; it merely upper-bounds the algorithm's stopping time by 4U*_epsilon. Even if the relaxation gap were closed, one would still need to justify that the lower bound with a 2epsilon separation is within a constant of the minimal sample complexity for the epsilon-PAC problem as stated in Definition 3.2. Please make this relationship explicit, or restrict the optimality statement accordingly.
minor comments (5)
- [Section 4 (introductory paragraph)] The claim that the lower bound 'constitutes the first such bound even for the single-policy single-reward case' is too strong as stated; prior single-reward PAC policy-evaluation bounds (e.g., Dann et al., Chen et al.) exist, and the novelty lies in the reward-dependent instance-specific form. Please hedge or qualify this claim with respect to the dependence on the reward value deviation.
- [Section 3.1, Additional notation paragraph] The abbreviation 'sim.' for 'similarly' appears in the notation paragraph; it should be written out for clarity.
- [Figure 2 caption] The y-axis label '∥VπMr− VπM′r(p2)∥∞' uses M' as a function of p2 but the notation is not defined; please clarify that the alternative model varies with p2 in the caption or in the text.
- [Algorithm 1, line 1] The stopping condition uses 'U_epsilon/2(N_t/t; M_t)', but the definition of U_epsilon in Eq. (6) takes an allocation omega; please add an explicit definition of the empirical object U_epsilon(N_t/t; M_t) in the text, or a pointer to the appendix where the empirical stopping rule is formalized.
- [Section 6 and Figures 3-4] The empirical evaluation reports estimation error over time but does not report the stopping time tau or compare the observed stopping time against the theoretical relaxed rate U*_epsilon; reporting this would let the reader assess whether the sample-complexity guarantee has practical relevance beyond the error-vs-time curves.
Circularity Check
No circularity: MR-NaS is matched to the relaxed rate U*, a defined optimization target, not a fitted input; the unproven U*/T* gap is a missing proof, not an input-output equivalence.
full rationale
The paper's derivation chain is not circular. Theorem 4.4 lower-bounds any (epsilon,delta)-PAC algorithm by T*_epsilon(M), the true characteristic time over confusing models, while Theorem 4.7 derives a convex upper bound U_epsilon via a Pinsker/Holder relaxation of the KL constraint, so U and T are distinct quantities. Theorem 5.2 bounds the algorithm by 4U*_epsilon(M), which is the quantity the algorithm optimizes (the sampling rule uses omega* = argmin U_{epsilon/2}), but that is the algorithm's own design target, not a parameter fitted to the data being 'predicted'. The value-deviation allocation omega ~ |rho|^2 follows from the relaxation proof, not from imposing the advertised scaling. The citation of Russo & Vannella (2024) for the MR-NaS scheme and the proof technique of Theorem 3.3 is a genuine self-citation, but the cited theorem is prior published work for multi-reward best policy identification and is used as an external template; the present claim is not assumed by it. The correctness caveat, which the paper itself flags, is that Section 4.3 states 'quantifying the gap |U_epsilon(omega; M) - T_epsilon(omega; M)| remains challenging, and we leave this analysis to future work', and Section 4.1 says 'we believe the looseness is at most a constant factor'. Without a proof that U*/T* is bounded by a constant, the Introduction's 'asymptotic optimality for policy evaluation up to a constant factor' is unsupported; Example 4.6 shows the confusing-model set can be non-convex, so the relaxation gap is substantive. This is a missing proof and a correctness risk, not circularity: no theorem assumes its own conclusion or converts a fitted value into a prediction.
Assumptions & free parameters
assumptions (5)
- domain assumption Assumption 3.1: the MDP is communicating and aperiodic under a uniform policy, and the learner has no prior knowledge of the transition function.
- domain assumption Assumption 4.3: for every state there exists a policy-reward pair with large one-step value deviation, ||rho^pi_r(s)||_inf > 2*epsilon/gamma.
- domain assumption Assumption 5.1: the optimal allocation omega* is unique and lies in the interior of the feasible set Omega(M).
- domain assumption The target policies are deterministic and finite, and the reward sets are finite or convex and known in advance.
- ad hoc to paper The relaxed characteristic time U_epsilon is within a constant factor of the true characteristic time T_epsilon.
Cite this review
Pith. "Pith review of Adaptive Exploration for Multi-Reward Multi-Policy Evaluation." pith.science (2026). https://pith.science/paper/NSQJECDN
@misc{pith2026250202516,
author = {Pith},
title = {Pith review of: Adaptive Exploration for Multi-Reward Multi-Policy Evaluation},
year = {2026},
howpublished = {\url{https://pith.science/paper/NSQJECDN}},
note = {Machine review of arXiv:2502.02516}
}
abstract
We study the policy evaluation problem in an online multi-reward multi-policy discounted setting, where multiple reward functions must be evaluated simultaneously for different policies. We adopt an $(\epsilon,\delta)$-PAC perspective to achieve $\epsilon$-accurate estimates with high confidence across finite or convex sets of rewards, a setting that has not been investigated in the literature. Building on prior work on Multi-Reward Best Policy Identification, we adapt the MR-NaS exploration scheme to jointly minimize sample complexity for evaluating different policies across different reward sets. Our approach leverages an instance-specific lower bound revealing how the sample complexity scales with a measure of value deviation, guiding the design of an efficient exploration policy. Although computing this bound entails a hard non-convex optimization, we propose an efficient convex approximation that holds for both finite and convex reward sets. Experiments in tabular domains demonstrate the effectiveness of this adaptive exploration scheme.
Figures
Figures from the paper (9 more)
Forward citations
Cited by 1 Pith paper
-
Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
First non-asymptotic sample-complexity upper bound for Navigate-and-Stop in tabular MDPs; recovers T(M)log(1/δ) as δ→0 and exposes sharpness, mixing, and connectivity as finite-δ costs.
Reference graph
Works this paper leans on
-
[1]
Define now the policy π(u|s) = P (u|s, π(s))
The reward function instead is ¯r(s) = r(s, π(s)). Define now the policy π(u|s) = P (u|s, π(s)). With M ¯r, we can convert the value of the policy under the original MDP and confusing models to the value of different policies under M ¯r. Specifically, the value of the policy π (deterministic) under the MDP Mr with transitions P is V π Mr (s) = V ¯π ¯M¯r (...
-
[2]
maxs V π r (s) − V π r (s′) ≤ (1 − λπ r ) maxs V π r (s) for any state s′. Proof. First, clearly λπ r ∈ [0, 1]. Then, the first property is derived from the following inequalities that hold for any pair (s, s′): λπ r V π r (s) ≤ λπ r max s V π r (s) = min s V π r (s) ≤ V π r (s′). The second statement stems from the simple fact that −V π r (s′) ≤ −mins V ...
-
[3]
V π r (s′) ≥ λπ r V π r (s) for any pair s, s′ ∈ S
-
[4]
Then, the sample complexity results follow from noting thatUϵ/2(ω; M ) = 4Uϵ(ω; M ) and applying the same methods as in Russo & Vannella (2024, Theorem 3.3) mutatis mutandis (which follows the proof technique of (Al Marjani et al., 2021)). C.2. Environment Details In this section we delve more into the detail of the numerical results for the tabular case....
work page 2024
-
[5]
We first prove ρπ r (s, s′) ≤ max 1, 1−λπ r 1−γ . Using that for any pair (s, s′) we have λπ r Ws′ ≤ Ws it follows that r(s′) + γWs′ − Ws = r(s′) + γWs′ − Ws ± λπ r Ws′, = r(s′) + (γ − λπ r )Ws′ + λπ r Ws′ − Ws| {z } ≤0 , ≤ r(s′) + (γ − λπ r )Ws′, ≤ 1 + max 0, γ − λπ r 1 − γ , ≤ max 1, 1 − λπ r 1 − γ
-
[6]
We now prove a lower bound onρπ r (s, s′). The idea is to seek a value of η ≥ 0 such that γWs′ − Ws ≥ (γ − 1)Wsη, which implies γWs′ − Ws ≥ −η (using that −Ws ≥ −1/(1 − γ)). Then, we find Ws′ ≥ (ηγ−η+1) γ Ws. Since Ws′ ≥ λπ r Ws, we can set (ηγ − η + 1) γ = λπ r ⇒ η = λπ r γ − 1 γ − 1 , (notably, if λπ r = γ, then η = 1 + γ ≤ 2). Lastly, we obtain ρπ r (s...
work page 2006
-
[7]
The forcing policy is chosen as πf,t(·|s) = softmax (−βt(s)Nt(s, ·)) with βt(s) = β log(Nt(s)) max(1,maxa |Nt(s,a)−minb Nt(s,b)|) , β∈ [0, 1] and (softmax(x))i = exi / P j exj for a vector x. This choice encourages to select under-sampled actions for β >0, while for β = 0 we obtain a uniform forcing policy πf,t(a|s) = 1/A. We then mix ω⋆ t with πf,t using...
work page 2024
-
[8]
We also note that the optimal solution ω⋆ satisfies ω⋆(s, a) > 0 for all (s, a). Then, such solution induces an ergodic (irreducible and aperiodic) chain by Assumption 3.1 and Assumption 5.1
Show all 14 references
-
[9]
We note that the solution ω⋆ is unique by Assumption 5.1
-
[11]
Draw without replacement three state-action pairs (s∗ i , a∗ i )3 i=1 uniformly from S × A
-
[12]
On the other hand, in the single-policy scenario we use a default target policy policy πdef that is different for each environment
Define the one-hot reward ri(s, a) = 1{(s, a) = (s∗ i , a∗ i )} and compute the target policy πi is computed via policy iteration on (M, ri). On the other hand, in the single-policy scenario we use a default target policy policy πdef that is different for each environment. Con...
-
[13]
For the reward free case we use Rcanon to perform evaluation
For each reward set (finite or reward-free) and each policy π, compute the true value V π Mr offline via value iteration on the known dynamics. For the reward free case we use Rcanon to perform evaluation
-
[14]
Compute the estimated value ˆV π r (t) by performing policy evaluation on ˆPt over the reward sets. 37 Adaptive Exploration for Multi-Reward Multi-Policy Evaluation 0.0 0.5 1.0 Time-steps ×106 10−2 10−1 100 E[maxπ,r‖ ˆV π r − V π r‖∞] Riverswim SF-NR GVFExplorer MR-NaS Noisy P...
-
[418]
Watkins, C
PMLR, 2022. Watkins, C. J. C. H. Learning from delayed rewards. PhD thesis, Cambridge University, Cambridge, England, 1989. Weissmann, S., Freihaut, T., Vernade, C., Ramponi, G., and D¨oring, L. Clustered kl-barycenter design for policy evaluation. arXiv preprint arXiv:2503.02...
2022 arXiv
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.