{"id":"e3022451-8a87-4448-827c-cbee06dcfe5c","arxiv_id":"1908.10479","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"EE-POLITEX interleaves an exploration policy with on-policy rollouts and uses least-squares Monte Carlo value estimation, claiming a sublinear regret bound under weaker exploration assumptions, but the proof has a norm-mismatch gap.","lead":"This paper proposes a version of the POLITEX reinforcement learning algorithm that mixes in a separate exploration policy to gather data, aiming for regret guarantees even when the learner's own policies do not explore. The main theorem is not fully established because the error bound proven is in a different norm than the one the regret argument requires.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1 requires value-estimation error in the reference policy's norms, but Lemma 4.2 proves the bound only in the exploration policy's norm; no assumption links μe to μ*, so the central regret bound is unsupported.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: the value-estimation error is proven in the norm weighted by the exploration policy's stationary distribution, but Theorem 3.1 requires it in the reference policy's stationary norms. Under Assumptions A1–A3, μe and μ* can have very different supports or weights; uniform mixing does not equate stationary distributions, and feature excitation (A3) is only about the exploration policy. Therefore the error guarantee from Lemma 4.2 cannot be substituted into Theorem 3.1. This is not a presentation issue: the paper's central theoretical contribution is the stated regret bound, and the proof links only if an implicit dominance condition holds, which is absent. The secondary concern about i.i.d. versus dependent samples from a single trajectory is real but less fundamental; it could plausibly be handled by existing mixing arguments. Since the main formal claim is unsupported by the provided proofs, and the experiments cannot validate a regret theorem, the REJECT verdict from the reader is appropriate. I see no need to change the verdict.","tokens_in":13106,"tokens_out":6965,"duration_ms":68653,"concrete_test":"Inspect the proof of Theorem 3.1 (given as a direct application of POLITEX's Theorem 4.1 to rounds excluding exploration) and identify every step where the value-estimation error is used. For each such step, replace the norm ‖·‖_{ν*} or ‖·‖_{μ*⊗πi} by the bound ‖·‖_{μe⊗u} from Lemma 4.2 and verify whether the step remains valid. Then construct a two-state, two-action MDP satisfying A1–A3 where πe's stationary distribution is concentrated on state 1 and π*'s is concentrated on state 2, with features separating the states; compute the error in both norms and determine whether the claimed O~(T^{4/5}) regret bound still follows. If any step requires a change of measure with an unbounded density ratio, the central claim is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is the O~(T^{4/5}+ε0T) regret bound. Theorem 3.1 (Eq. 3) requires, for every phase i and with probability 1−δ, that ‖Qπi−Q̂i‖_{ν*} ≤ ε(δ,m) and ‖Qπi−Q̂i‖_{μ*⊗πi} ≤ ε(δ,m), where ν*=μ*⊗π* is the reference policy's stationary state-action distribution. Lemma 4.2, however, establishes the bound only in the exploration policy's norm: ‖Ψ(ŵ−w̃)‖_{μe⊗u} = O(σ^{-1/2}√(log(1/δ)/m)), which with the irreducible error gives ‖Qπ−Q̂‖_{μe⊗u} ≤ ε0 + C√(log(1/δ)/m). No assumption in A1–A3 relates μe to μ*; uniform mixing bounds convergence rates, not stationary distributions, and A3 only requires λ_min(Ψ^T D_{νπe} Ψ) ≥ σ. The regret theorem must control errors on state-action pairs under π*, while the estimator is only guaranteed accurate under πe. The paper even states in §2.2 that it will bound the error 'in the norm weighted by [πe's] stationary distribution' without reconciling this with the norms appearing in Theorem 3.1. Thus the transfer from μe⊗u to ν* is unjustified and the main theoretical contribution is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes EE-POLITEX, a modification of the POLITEX algorithm for average-cost reinforcement learning with linear function approximation. The key idea is to replace the assumption that all policies sufficiently explore with the assumption that a single exploration policy is available, and to interleave short exploration segments with on-policy rollouts of the current target policy. The value function is estimated by least-squares Monte Carlo (LSMC) from data whose initial states are approximately drawn from the exploration policy's stationary distribution. The paper claims a regret bound of O~(T^{4/5} + ε0 T) under assumptions A1–A3, and presents experiments on DeepSea and a sparse Cartpole task to illustrate the benefits of explicit exploration.","tokens_in":13450,"tokens_out":6810,"duration_ms":62331,"significance":"The algorithmic idea is attractive: separating exploration from reward maximization and using a single exploratory policy to provide coverage is a useful conceptual step, and the modular 'soft reset' scheme could be of independent interest. If the regret bound were rigorously established, it would extend POLITEX-style guarantees to settings where uniform exploration by all policies is unrealistic. The LSMC estimation procedure with on-policy rollouts from exploration-sampled initial states is also a sensible construction. However, the central theoretical claim is not currently supported: the regret theorem requires value-estimation error in norms weighted by the reference policy, while the estimation lemma only provides a bound in the exploration policy's norm. The i.i.d. assumption in the estimation lemma also does not match the dependent trajectory produced by the algorithm. As a result, the main contribution is not established in the present form.","major_comments":[{"comment":"Theorem 3.1 requires, for every phase i and with probability 1−δ, that ‖Q_{π_i}−Q̂_i‖_{ν*} ≤ ε(δ,m) and ‖Q_{π_i}−Q̂_i‖_{μ*⊗π_i} ≤ ε(δ,m), where ν*=μ*⊗π* is the stationary state-action distribution of the reference policy. Lemma 4.2, however, establishes the bound only in the norm ‖·‖_{μ_e⊗u}, weighted by the exploration policy's stationary distribution. Assumptions A1–A3 do not relate μ_e to μ*: A2 is a mixing-rate condition, and A3 only lower-bounds λ_min(Ψ^T D_{ν_{π_e}} Ψ). Without an additional coverage or density-ratio condition, an error bound in the μ_e⊗u norm does not control the error in the ν* or μ*⊗π_i norms. The paper's own Section 2.2 states that the goal is to bound the error in the ν_{π_e}-weighted norm, which underscores the mismatch. This gap directly undermines the main regret guarantee.","section":"§3.1, Eq. (3) and §4.1, Lemma 4.2"},{"comment":"Lemma 4.2 assumes that the m state-action pairs (x_j,a_j) are independent draws from μ_e⊗u; its proof explicitly refers to 'm i.i.d. samples.' Algorithm 1, however, obtains x_j by running a single trajectory with alternating exploration and target-policy segments, so successive x_j are neither exactly stationary nor independent. The choice s′=log T suggests approximate stationarity under A2, but the paper provides no argument quantifying the total-variation distance to stationarity or controlling the dependence among samples. As stated, the lemma does not apply to the data actually produced by Algorithm 1, so the estimation error bound used in the regret analysis is unsupported.","section":"§4.1, Lemma 4.2 and Algorithm 1 (COLLECT DATA)"},{"comment":"The lemma states 'Under the assumption that ‖Ψ^T DΨ‖ ≥ σ', but the proof uses the inverse of Ψ^T DΨ, so the required hypothesis is that the smallest eigenvalue of Ψ^T DΨ is at least σ (as in Assumption A3), not that the matrix norm is at least σ. As written, the hypothesis is both misstated and insufficient: the matrix norm is the largest singular value, and its being large does not guarantee invertibility with a controlled inverse.","section":"§4.1, Lemma 4.2, hypothesis"}],"minor_comments":[{"comment":"The symbol μ* is used in the theorem and in the definition of S_δ(A,μ*) without being defined there; it should be stated explicitly that μ* is the stationary distribution of the reference policy π*.","section":"§3.1, Theorem 3.1"},{"comment":"The claim that this is 'the first result that shows how to control the regret in the presence of function approximation errors on problems where exploration is nontrivial' is not substantiated and is difficult to verify; it would be safer to phrase the contribution more modestly.","section":"Abstract"},{"comment":"There is a discrepancy between the lemma statement and its proof: the lemma states |V_T| ≤ nmκ + 4nκ√(4ms log(2ms/δ)), while the proof concludes |V_T| ≤ 2nmκ + 4nκ√(4ms log(2m(s+s′)/δ)). The extra factor of 2 must be reconciled.","section":"Lemma 3.2 and Appendix A"},{"comment":"The y-axis of Figure 1 is labeled 'cost' but the text says 'all policies achieve the lowest cost' in a regime where plotted values are negative; the sign convention should be clarified so the reader knows whether lower or higher values are better.","section":"§5.1, Figure 1"},{"comment":"In the Cartpole experiment, the exploration policy is trained with a separate reward function, whereas the theory assumes a given exploration policy. The text should clarify whether the experiments are intended only as an illustration or whether the theory is claimed to extend to learned exploration policies.","section":"§5.2"}],"recommendation":"reject","confidential_remarks":"The norm-mismatch gap in the proof of the main regret theorem is fundamental: no assumption in the paper links the exploration policy's stationary distribution to that of the reference policy, so Lemma 4.2 cannot supply the error bound required by Theorem 3.1. Adding a density-ratio or coverage assumption would be a substantive change to the contribution and would weaken the advertised generality. The i.i.d. sampling issue is also unresolved. I do not see a path to mending these gaps within the current manuscript's scope; the paper would need a substantially revised analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nShort version: this paper deserves a serious referee, but not acceptance in this form. The EE-POLITEX loop is a clean modular extension of POLITEX, and the LSMC estimator with exploration resets is a genuinely useful idea. The problem is that the main theorem and the estimation lemma are in different norms, and no assumption connects them.\n\nTheorem 3.1, via Eq. (3), needs ||Qπi − Q̂i||_{ν*} and ||Qπi − Q̂i||_{μ*⊗πi} to be O(ε(δ,m)), where ν* is the reference policy's stationary state-action distribution. Lemma 4.2 proves ||Ψ(ŵ − w̃)||_{μe⊗u} = O(σ^{-1/2}√(log(1/δ)/m)), with νe = μe⊗u the exploration distribution. That is not a matter of constants: the two norms are weighted by different stationary distributions, and Assumptions A1–A3 contain nothing relating μe to μ*. Uniform mixing bounds convergence to stationarity, not the stationary distributions themselves; A3 only requires the features to be excited under πe. The paper's own §2.2 says the goal is to bound the error in the norm weighted by the exploration policy's stationary distribution, but that is exactly the norm that does not appear in Theorem 3.1. So the regret bound O~(T^{4/5}+ε0T) is not established by the arguments given.\n\nThere is a secondary, smaller gap: Lemma 4.2's proof treats the m samples as i.i.d. draws from μe, but Algorithm 1 produces them from one dependent trajectory with soft resets. That is likely fixable with a mixing-time burn-in argument, but it is currently unstated.\n\nWhat is genuinely good: the method is simple and modular, the LSMC error analysis avoids the contraction-coefficient and fixed-point artifacts that plague LSPE/LSTD bounds, and the DeepSea/cartpole experiments illustrate the intended benefit of explicit exploration. The citation pattern is reasonable; the paper leans on the authors' own POLITEX theorem, but that is prior peer-reviewed work and using it as a black box is legitimate.\n\nThis is a fixable paper, not a dead end. The fix is to add an explicit assumption relating μe and μ*, or to prove the estimation error in the norms Theorem 3.1 actually requires. A good referee should ask for that revision. Sending it out is appropriate; accepting it now would be premature.","headline":"EE-POLITEX is a promising modular idea, but the headline regret bound is not established because the value-estimation error is proved in the exploration policy's norm while the regret theorem needs it in the reference policy's norms.","tokens_in":13934,"tokens_out":2468,"would_cite":false,"duration_ms":22927,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that one pre-existing exploration policy, interleaved with policy iteration, suffices to keep regret sublinear without requiring every learned policy to explore.","keywords":["average-cost reinforcement learning","regret bounds","policy iteration","POLITEX","exploration policy","least-squares Monte Carlo","function approximation","uniformly mixing MDPs"],"falsifier":"Construct a unichain MDP with two nearly disjoint recurrent regions: the exploration policy mixes fast and excites all features in region A, while the reward-optimal baseline and all learned policies stay in region B. Then compute $\\|Q_{\\pi_i}-\\Psi\\hat{w}\\|$ under $\\mu_*\\otimes\\pi_i$ as $m$ grows. If the error fails to decay at the claimed $O(\\sqrt{\\log(1/\\delta)/m})$ rate, the premise of Theorem 3.1 is violated.","tokens_in":12937,"feed_emoji":"🧭","tokens_out":16227,"duration_ms":150577,"temperature":0.7,"pith_summary":"The paper modifies POLITEX, a policy-iteration algorithm whose policy is near-optimal in hindsight for past value estimates, so that only one pre-existing exploration policy needs to cover the state space; all other policies are free to be greedy. In uniformly mixing average-cost MDPs with linear value function approximation, the resulting EE-POLITEX has regret $\\tilde{O}(T^{4/5}+\\epsilon_0 T)$, where $\\epsilon_0$ is the irreducible linear approximation error. This matters because prior guarantees required every learned policy to explore, which is unrealistic when policies control where they go. The proof works by alternating short exploration runs with target-policy rollouts — the exploration acts as soft resets — and by estimating value functions with least-squares Monte Carlo from those rollouts. Experiments on DeepSea and cartpole swing-up show the scheme succeeds where dithering-based exploration does not.","feed_headline":"One exploration policy is enough for sublinear RL regret","feed_subtitle":"EE-POLITEX alternates short exploration runs with policy iteration and keeps regret near O~(T^{4/5}).","key_machinery":"The load-bearing object is the data-collection schedule of EE-POLITEX combined with a least-squares Monte Carlo (LSMC) estimator. Each phase alternates $s'$ exploration steps with $s$ on-policy steps, so initial states of the rollouts are approximately i.i.d. from $\\mu_e$ and state-action pairs are distributed as $\\nu=\\mu_e\\otimes u$. The estimator solves $\\hat{w}=\\arg\\min_w \\sum_j (Q^*_{\\pi}(x_j,a_j)-w^{\\top}\\psi(x_j,a_j))^2$, with $Q^*_{\\pi}$ formed from finite-rollout differential costs. The main identity is the error decomposition in Equation (10), which separates the estimation error into a statistical fluctuation term between empirical and true feature covariance and a rollout-bias term; the uniform excitation condition $\\sigma$ on $\\Psi^{\\top} D_{\\nu_e}\\Psi$ keeps the inverse covariance bounded. This avoids the projected-Bellman contraction coefficient that can make TD/LSPE bounds vacuous.","core_discovery":"The central claim is that the exploration burden in POLITEX can be moved from all policies to a single fast-mixing exploration policy $\\pi_e$. Given $\\pi_e$ whose stationary distribution excites every feature direction (Assumption A3), EE-POLITEX runs $\\pi_e$ for $s'=\\log T$ steps, samples an initial state-action pair, then runs the current policy for $s=T^{1/5}$ steps to produce an on-policy trajectory; with $n=m=T^{2/5}$ phases, the regret against a reference policy $\\pi_*$ is $\\tilde{O}(T^{4/5}+\\epsilon_0 T)$ under uniform mixing. The proof decomposes regret into pseudo-regret, exploration cost, and two mixing-noise terms, and shows that a least-squares Monte Carlo value estimator achieves $\\|Q_{\\pi}-\\Psi\\hat{w}\\|_{\\mu_e\\otimes u}=O(\\sqrt{\\log(1/\\delta)/m})$ plus a term controlled by $\\epsilon_0$. The paper presents this as the first regret bound for function-approximation RL where exploration is nontrivial but only a single known policy needs to explore.","pith_inferences":["The proof would be complete if an assumption linked the baseline distribution $\\mu_*$ to the exploration distribution $\\mu_e$, for instance absolute continuity with a bounded density; without that, the bound in Lemma 4.2 does not formally imply Theorem 3.1's premise.","The analysis treats rollout-start states as i.i.d. draws from $\\mu_e$ even though Algorithm 1 generates them from one dependent path; a fully formal version would have to absorb the uniform-mixing penalty into the LSMC concentration argument.","The modular framing suggests a practical design rule: spend a no-reward phase learning a policy that spans the feature space, then plug it into EE-POLITEX for reward optimization. This could be tested on continuous-control benchmarks where dithering provably fails.","Extending Lemma 4.2 to nonlinear value function classes would turn the neural experiments into a theorem; this is the most natural next step but is not carried out in the paper."],"forward_implications":["Up to the unavoidable $\\epsilon_0 T$ approximation term, per-round regret decays as $T^{-1/5}$, so the method is no-regret when the linear value function error is negligible.","The feature-excitation assumption is needed only for the single exploration policy, not for the policies being learned, which is what improves on POLITEX.","The exploration cost and noise terms can be balanced at $n=m=T^{2/5}$, giving a concrete hyperparameter recipe for implementing the algorithm.","The value estimation is modular: any estimator satisfying the $\\nu_e$-weighted error bound in Eq. (3) can be plugged into EE-POLITEX and inherit the regret guarantee."],"supporting_citations":[{"why":"It supplies the base POLITEX algorithm, the regret decomposition, and Theorem 4.1 that Theorem 3.1 adapts with exploration.","marker":"Abbasi-Yadkori et al. [2019a]"},{"why":"It defines LSPE, the value estimator whose error guarantee motivated the original uniform-exploration assumption.","marker":"Bertsekas and Ioffe [1996]"},{"why":"It establishes the contraction of projected TD in average cost, the coefficient that makes prior bounds potentially vacuous.","marker":"Tsitsiklis and Van Roy [1999]"},{"why":"It quantifies the extra approximation error of TD fixed points relative to the best linear fit, motivating direct least-squares Monte Carlo.","marker":"Yu and Bertsekas [2010]"},{"why":"It gives a convergence result for off-policy LSTD only in discounted problems, framing the average-cost gap this paper addresses.","marker":"Yu [2010]"},{"why":"It provides the DeepSea environment and the RLSVI baseline used to demonstrate the benefit of explicit exploration.","marker":"Osband et al. [2016]"}],"fun_headline_variants":["One explorer powers sublinear regret in RL","EE-POLITEX: single exploration policy suffices","Sublinear regret with a single exploration policy","POLITEX gets by with one exploration policy","One exploration policy: key to RL regret bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theorem's premise is that value-estimation error is small under the baseline policy's stationary distribution, but the proof bounds it only under the exploration policy's distribution, and no stated assumption forces one to imply the other.","fun_headline_variants_meta":{"raw":{"variants":["One explorer powers sublinear regret in RL","EE-POLITEX: single exploration policy suffices","Sublinear regret with a single exploration policy","POLITEX gets by with one exploration policy","One exploration policy: key to RL regret bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000773,"raw_usage":{"total_tokens":3480,"prompt_tokens":1059,"completion_tokens":2421,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":2350}},"tokens_in":675,"tokens_out":2421,"duration_ms":18481,"temperature":1.0,"reasoning_tokens":2350,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:43:32.810856+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a unichain MDP with two nearly disjoint recurrent regions: the exploration policy mixes fast and excites all features in region A, while the reward-optimal baseline and all learned policies stay in region B. Then compute $\\|Q_{\\pi_i}-\\Psi\\hat{w}\\|$ under $\\mu_*\\otimes\\pi_i$ as $m$ grows. If the error fails to decay at the claimed $O(\\sqrt{\\log(1/\\delta)/m})$ rate, the premise of Theorem 3.1 is violated.","supporting_citations":[{"cited_title":"Temporal differences-based policy iteration and applications in neuro-dynamic programming","cited_arxiv_id":null,"evidence_quote":"It defines LSPE, the value estimator whose error guarantee motivated the original uniform-exploration assumption."},{"cited_title":"Error bounds for approximations from projected linear equations","cited_arxiv_id":null,"evidence_quote":"It quantifies the extra approximation error of TD fixed points relative to the best linear fit, motivating direct least-squares Monte Carlo."},{"cited_title":"Generalization and exploration via randomized value functions","cited_arxiv_id":null,"evidence_quote":"It provides the DeepSea environment and the RLSVI baseline used to demonstrate the benefit of explicit exploration."}],"review_version":1}