{"id":"eaeee579-4598-4e35-a05e-c627c579e84b","arxiv_id":"2606.20107","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantile-of-means ensemble method achieves minimax optimal variance-dependent regret bounds for finite-horizon MDPs without count-based uncertainty estimates.","lead":"The paper proposes a quantile-based ensemble method for exploration in finite-horizon MDPs that achieves optimal variance-dependent regret without using count-based bonuses. A smart generalist might read it to see how ensemble techniques can receive theoretical support in RL, potentially simplifying practical algorithm design.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Extension of quantile-of-means from MABs to finite-horizon MDPs may require unstated assumptions on ensemble size, variance estimation, or error propagation over horizon H to retain optimal variance-dependent regret.","rationale":"The reader's weakest assumption directly identifies the load-bearing step. Because the full text is referenced but the abstract supplies no proof sketch, the same gap remains the most direct threat to the central claim; no other internal inconsistency is visible from the given material.","tokens_in":1576,"tokens_out":341,"duration_ms":24627,"concrete_test":"Locate the main regret theorem (likely Theorem 4.x or similar) and its proof; extract the step that reduces the MDP regret to the MAB quantile bound. Re-derive that step assuming only the stated ensemble construction and check whether an extra H factor or additional variance term appears; if the final bound matches the minimax variance-dependent lower bound exactly, the extension holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim is that the count-free quantile ensemble achieves optimal variance-dependent regret bounds for finite-horizon MDPs. For this to hold, the per-step quantile estimate must induce exploration whose cumulative effect matches known lower bounds (typically involving sqrt(V* H^3 S A T) or variance-dependent variants) without count-based bonuses. The MAB analysis does not address value-function backups or horizon-dependent concentration; if the paper's MDP proof simply invokes the bandit result without new lemmas controlling the propagation of quantile errors across H steps or the dependence on the unknown transition kernel, the optimality claim rests on an implicit assumption that is not guaranteed by the abstract.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes a quantile-of-means ensemble method for exploration in finite-horizon MDPs. Extending a recent count-free ensemble approach from multi-armed bandits, the method is claimed to achieve minimax-optimal variance-dependent regret bounds without relying on count-based bonuses or explicit uncertainty estimates.","tokens_in":1695,"tokens_out":428,"duration_ms":10884,"significance":"If the central claims hold with rigorous proofs, the result would be significant: it supplies the first theoretical justification for a practical ensemble heuristic in RL while matching known optimal variance-dependent rates (typically of the form involving sqrt(V* H^3 S A T) or similar). This bridges the gap between count-based theory and ensemble practice and could influence algorithm design.","major_comments":[{"comment":"The extension from the MAB setting to finite-horizon MDPs requires explicit control of quantile-estimate errors across the horizon H and through value-function backups; without new concentration lemmas addressing propagation through the unknown transition kernel, the optimality claim rests on an implicit assumption that the per-step bandit guarantee lifts directly (see skeptic note on horizon-dependent concentration).","section":"MDP analysis / main regret theorem"},{"comment":"It is unclear whether the ensemble construction (size, quantile level, or variance handling) is independent of state-action visit counts or requires additional assumptions on the MDP to retain the variance-dependent bound; any hidden dependence would undermine the 'count-free' and 'bonus-free' claims.","section":"§3 (method) and regret proof"}],"minor_comments":[{"comment":"Clarify all assumptions on the MDP (finite horizon, bounded rewards, etc.) and ensemble parameters in the main text rather than deferring to the bandit reference.","section":null},{"comment":"Ensure experimental sections (if present) report variance-dependent metrics and compare against both count-based and other ensemble baselines with statistical significance.","section":null}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their constructive comments on our manuscript. We are pleased that the potential significance of the result is recognized. Below we provide point-by-point responses to the major comments.","responses":[{"response":"The proof of the main regret theorem (Theorem 4.1) does include dedicated concentration lemmas for the propagation of quantile estimation errors over the horizon. In particular, we develop a new martingale concentration result (Lemma 4.2) that accounts for the dependence through the unknown transition kernel in the value function backups. This allows the per-step guarantees to be lifted rigorously to the full horizon without additional assumptions. We can add a pointer to these lemmas in the main text if it helps clarify the structure.","revision_made":"partial","referee_comment":"[MDP analysis / main regret theorem] The extension from the MAB setting to finite-horizon MDPs requires explicit control of quantile-estimate errors across the horizon H and through value-function backups; without new concentration lemmas addressing propagation through the unknown transition kernel, the optimality claim rests on an implicit assumption that the per-step bandit guarantee lifts directly (see skeptic note on horizon-dependent concentration)."},{"response":"The ensemble parameters are chosen independently of visit counts. Section 3 specifies that the number of ensemble members and the quantile level are absolute constants that do not depend on n(s,a) or any other state-action specific quantities. The variance-dependent bound is derived directly from the quantile-of-means estimator without invoking count-based terms. No extra MDP assumptions are used. To address the lack of clarity, we will revise Section 3 to explicitly state the independence from visit counts.","revision_made":"yes","referee_comment":"[§3 (method) and regret proof] It is unclear whether the ensemble construction (size, quantile level, or variance handling) is independent of state-action visit counts or requires additional assumptions on the MDP to retain the variance-dependent bound; any hidden dependence would undermine the 'count-free' and 'bonus-free' claims."}],"tokens_in":1195,"tokens_out":442,"duration_ms":34847,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The core contribution is a direct application of the quantile-of-means idea to finite-horizon MDPs, producing a count-free method that the authors say matches known optimal regret bounds. This is new in the sense that the prior bandit work did not cover value-function backups or multi-step error accumulation.\n\nWhat the paper does cleanly is remove the need for explicit visit counts while still targeting variance-dependent bounds, which aligns with practical interest in ensemble-based exploration. If the math closes, it supplies a concrete justification for why simple ensembling can work in RL without ad-hoc bonuses.\n\nThe soft spot is exactly the one flagged in the stress test. Bandit concentration does not automatically carry over to MDPs because quantile errors can compound across the horizon H through the transition kernel and value estimates. Without explicit lemmas that bound how those per-step quantile deviations propagate and interact with the unknown dynamics, the optimality claim rests on an implicit assumption that the bandit result suffices. I would check whether the proof introduces new concentration arguments or simply invokes the earlier result.\n\nThe work is aimed at RL theorists who track regret analyses and ensemble techniques. A reader already familiar with the bandit quantile paper will see the extension immediately and can judge the technical lift. It is worth sending to peer review so the details on error propagation get checked by people who work on finite-horizon bounds; the claim is sharp enough to merit that step even if revisions follow.","headline":"The paper lifts quantile-of-means ensembles from bandits to finite-horizon MDPs and claims optimal variance-dependent regret without counts, but the horizon error handling is the part that needs verification.","tokens_in":2141,"tokens_out":366,"would_cite":false,"duration_ms":18288,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"A quantile of means from an ensemble achieves minimax optimal regret bounds in finite-horizon MDPs without count-based bonuses.","keywords":["reinforcement learning","ensemble methods","regret bounds","exploration","finite-horizon MDPs","quantile estimation","variance-dependent regret"],"falsifier":"Running the algorithm on a finite-horizon MDP where the observed regret significantly exceeds the variance-dependent bound predicted by the theory.","tokens_in":2471,"feed_emoji":"","tokens_out":516,"duration_ms":20555,"temperature":0.7,"pith_summary":"The paper proposes replacing count-based uncertainty bonuses with a quantile of means drawn from an ensemble of value estimates. This approach extends a bandit method to finite-horizon MDPs and is shown to attain the optimal variance-dependent regret. A sympathetic reader would care because it gives theoretical support to a practical heuristic that avoids the computational difficulties of exact counts in large state spaces. If correct, it means ensemble methods can be used confidently for exploration in RL without sacrificing optimality.","feed_headline":"Quantile of means gives optimal RL regret without counts","feed_subtitle":"Ensemble method for finite-horizon MDPs matches variance-dependent theoretical bounds.","key_machinery":"The quantile of means, which selects a conservative estimate from multiple independent value function estimates to guide exploration.","core_discovery":"The quantile of means estimator, when applied to an ensemble in finite-horizon MDPs, yields a bonus-free exploration strategy that attains the minimax optimal regret bound which depends on the variance of the returns.","pith_inferences":["Similar quantile ensembles might work in infinite-horizon or continuous state settings if the finite-horizon analysis can be adapted.","The method could be combined with deep neural network ensembles to scale to complex environments.","Testing the variance dependence in practice could reveal whether the theoretical improvement translates to faster learning in high-variance tasks."],"forward_implications":["It achieves optimal variance-dependent regret bounds.","It eliminates the need for explicit count-based uncertainty estimates.","It extends ensemble methods from multi-armed bandits to MDPs while preserving optimality.","It provides theoretical justification for using ensembles in reinforcement learning exploration."],"fun_headline_variants":["Quantile of means powers bonus-free optimal regret in RL ensembles","Count-free quantile ensemble attains minimax RL regret bounds","Quantile means boost MDPs to variance-dependent optimal regret","Ensemble with quantile of means achieves bonus-free minimax optimality"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"That the properties of the ensemble method carry over from bandits to MDPs without needing extra structure or assumptions on how the ensemble is built.","fun_headline_variants_meta":{"raw":{"variants":["Quantile of means powers bonus-free optimal regret in RL ensembles","Count-free quantile ensemble attains minimax RL regret bounds","Quantile means boost MDPs to variance-dependent optimal regret","Ensemble with quantile of means achieves bonus-free minimax optimality"]},"model":"grok-4.3","cost_usd":0.003044,"raw_usage":{"total_tokens":1574,"prompt_tokens":498,"num_sources_used":0,"completion_tokens":65,"cost_in_usd_ticks":30437000,"prompt_tokens_details":{"text_tokens":498,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1011,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":498,"tokens_out":65,"duration_ms":7193,"temperature":1.0,"reasoning_tokens":1011,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T18:16:52.441857+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Running the algorithm on a finite-horizon MDP where the observed regret significantly exceeds the variance-dependent bound predicted by the theory.","supporting_citations":[],"review_version":1}