{"id":"c2ba592a-935b-4d9f-af32-44d77c069605","arxiv_id":"2505.07101","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A general framework and algorithm for constrained contextual online decision-making with regret bounds expressed in terms of a generalized eluder dimension and an offline density estimation oracle.","lead":"This paper proposes GED-UCB, a unified algorithm for sequential decision-making where every round's action must satisfy a feasibility constraint, using any offline density estimation oracle. It extends the eluder dimension complexity measure to probability divergences and claims regret bounds for constrained bandits, active learning, hypothesis testing, and calibration.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7.6's third regret term is not derived: Lemma B.2 bounds realized-pair divergence amplitudes, not the expected policy-level width, and the stated bound drops the r_T factor.","rationale":"The reader's weakest assumption identifies exactly the step I also find load-bearing: the proof of Theorem 7.6 asserts that the constraint-uncertainty term is controlled by Lemma B.2 without deriving how the policy-level, expectation-over-context width is bounded by the generalized eluder dimension of the realized sequence. My independent reading confirms the gap and adds a concrete detail: the stated application also drops the r_T factor present in Lemma B.2. This is not cosmetic: for the oracle in Theorem 9.2, EstOff_D(G,T,δ/2T³) = log(|G|T³/δ), which can exceed 1, so restoring the factor changes the leading dependence of the α_r term. The omitted factor, together with the missing argument for the expectation over x, means the central regret bound is unproven as written. I also note a separate correctness issue in Theorem 9.1: the sum of squared Hellinger distances is reported as O(σ²(d+...)), but the Hellinger-squared denominator scales as 1/σ² while the least-squares prediction error scales as σ², so the correct bound should be dimension-controlled rather than proportional to σ². This example oracle is secondary to the main theorem but reinforces the need for a careful revision. None of this changes the reader's verdict: the framework and the generalized eluder dimension are plausible, but the main theorem is not established by the provided proof.","tokens_in":34750,"tokens_out":9807,"duration_ms":99281,"concrete_test":"Re-derive the last display of Theorem 7.6 by replacing the asserted application of Lemma B.2 with the lemma's actual statement, keeping r_T = EstOff_D(G,T,δ/2T³) and treating the policy-level term as ∑_t E_x sup_{g',g''} [\\tilde T₂(g'_x,π_t)−\\tilde T₂(g''_x,π_t)] rather than ∑_t ω_{G_t}(x_t,a_t). If the calculation yields an extra √r_T factor or requires a new lemma to move from realized-pair amplitudes to the expectation over x, then the displayed O(·) regret bound does not follow from the paper's current lemmas and the proof must be revised before Theorem 7.6 can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"At the end of the proof of Theorem 7.6 (Appendix C), the decisive step is: \"we apply lemma B.2 to get E_{x_t∼Q,a_t∼π_t}[max_{g',g''∈\\tilde C_G(t,δ)}(T₂(g'_{x_t,a_t})−T₂(g''_{x_t,a_t}))] ≤ C min{dimE(G,D,1/T²),T}+4√(dimE(G,D,1/T²)T)+1.\" This does not follow from Lemma B.2 as stated. Lemma B.2 is a high-probability bound on the sum ∑_{t=1}^T ω_{G_t}(x_t,a_t), where ω is the D-amplitude at the realized pair (x_t,a_t) and G_t is defined with radius r_t. The term in Theorem 7.6 is instead a sum over t of expectations over a fresh context x of the policy-level width sup_{g',g''} [T₂(g'_x,π_t)−T₂(g''_x,π_t)]. No argument is supplied to pass from realized-pair amplitudes to expectations of max-over-action widths, and no concentration step for the expectation over x is shown. Moreover, the displayed application omits the factor √r_T that Lemma B.2 carries; with the confidence set actually used, r_T = EstOff_D(G,T,δ/2T³), the third regret term would be α_r(1/T + C min{dimE,T} + 4√(EstOff_D(G,T,δ/2T³)·dimE·T)), not the bound stated in Theorem 7.6. Since this is the only step controlling the α_r term, the stated regret bound is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a unified framework for online contextual decision-making with stage-wise feasibility constraints. The learner observes a context, selects a stochastic policy over a finite action set, and must keep a constraint functional below a threshold with high probability while maximizing a utility functional. The main contribution is GED-UCB, an algorithm combining an offline density-estimation oracle, a counterfactual upper-confidence-bound selection rule, and a generalized notion of the eluder dimension defined for arbitrary metric-like divergences between conditional densities. The authors claim that GED-UCB achieves high-probability feasibility for all rounds and an expected-utility regret bound of order O(2 β_T (K + log(T/K)) + 2K β_T log T + α_r(1/T + C min{T, dim_E(G,D,1/T^2)} + 4 sqrt(dim_E(G,D,1/T^2) T))), with instantiations for linear density classes, Gaussian families, and exponential families, as well as offline oracles based on least squares and maximum likelihood.","tokens_in":35026,"tokens_out":12920,"duration_ms":136504,"significance":"If the main theorem were established, the paper would make a useful conceptual contribution: the generalized eluder dimension for density classes under metric-like divergences is a natural extension of Russo and Van Roy's eluder dimension, and the oracle-efficient design is appealing because it avoids strong online-oracle assumptions. The paper also demonstrates a broad range of potential applications, including constrained bandits, active learning with label budgets, online hypothesis testing, and sequential calibration. The modular lemma structure and the inclusion of complete proofs in the appendix are strengths. However, the load-bearing steps of the proof of the central regret bound are not currently justified, and the feasibility claim is internally inconsistent with the algorithm's own warm-up phase, so the advertised guarantees are not established as written.","major_comments":[{"comment":"The final step controlling the α_r term is unsupported. The proof writes 'we apply lemma B.2 to get E_{x_t∼Q,a_t∼π_t}[max_{g',g''∈C_G(t,δ)}(T2(g'_{x,a_t})−T2(g''_{x,a_t}))] ≤ C min{dim_E(G,D,1/T^2),T} + 4√(dim_E(G,D,1/T^2)T) + 1.' But Lemma B.2 bounds the realized-pair sum ∑_{t=1}^T ω_{G_t}(x_t,a_t), where G_t is defined with radius r_t and ω is the pointwise divergence amplitude at the realized pair (x_t,a_t). The term in Theorem 7.6 is instead a sum over t of expectations over fresh contexts x of the policy-level width max_{g',g''}[tilde T2(g'_x,π_t)−tilde T2(g''_x,π_t)]. No argument is supplied to pass from realized-pair amplitudes to expectations of max-over-action widths under the randomized policy, and no concentration step for the expectation over x is shown. Moreover, the displayed application omits the √r_T factor carried by Lemma B.2; with the confidence set used in Algorithm 1, r_T = EstOff_D(G,T,δ/2T^3), so the bound would need an EstOff-dependent factor. This step is the only control of the α_r term, so Theorem 7.6(2) as stated does not follow from the presented lemmas.","section":"Appendix C, proof of Theorem 7.6"},{"comment":"The claimed feasibility guarantee contradicts the algorithm's warm-up phase. Algorithm 1 says 'for round t = 1,···,K do Choose action a_t regardless of context x_t', and Section 6.2 explicitly states that this initial phase 'may lead to constraint violations (i.e., infeasible actions)'. Theorem 7.6(1) nevertheless claims that with probability at least 1−δ the entire policy sequence {π_t}_{t=1}^T selected in Algorithm 1 is feasible. This is internally inconsistent. Either the feasibility claim must be restricted to t>K, or the warm-up phase must be modified to use only the safe action a0.","section":"Algorithm 1 and Theorem 7.6(1)"},{"comment":"The stated offline oracle bound for least-squares Gaussian regression has the wrong dependence on σ². For two Gaussians with the same variance σ², the squared Hellinger distance behaves as D_H^2 ≈ ((θ*−θ̂)^T φ)^2/(8σ²). The proof's basic inequality gives ||Φθ*−Φθ̂||_2^2 ≤ O(σ²(d+√(d log(1/δ))+log(1/δ))). Combining these two facts yields a sum of Hellinger distances of order O(d+√(d log(1/δ))+log(1/δ)), not O(σ²(d+√(d log(1/δ))+log(1/δ))). The theorem as written is therefore dimensionally inconsistent, and the EstOff bound derived from it needs to be corrected or the Hellinger normalization must be clarified.","section":"Theorem 9.1"},{"comment":"The regret definition in Section 3 and the statements of Lemmas 7.2, 7.5, and Theorem 7.6 evaluate policies at fresh contexts x∼Q_x, but Algorithm 1 constructs π_t(·|x_t) only for the realized context x_t via the counterfactual simulation loop. The manuscript does not specify how π_t is extended to a mapping X→Δ(A). If the intent is to define π_t(x) by running the same counterfactual argmax rule for every x, that extension is not stated in the algorithm and is potentially infinite-dimensional. This gap affects the interpretation of the expected regret and the validity of the E_{x∼Q} steps in the proofs.","section":"Section 3 and Section 6.2"}],"minor_comments":[{"comment":"The displayed bound contains the expression T2(g'(x,π_t,y))−T2(g''(x,π_t,y)), where y is not defined; it should be written as max_{g',g''∈C_G(t,δ)} [tilde T2(g'_x,π_t)−tilde T2(g''_x,π_t)].","section":"Theorem 7.6 statement"},{"comment":"Assumption 5.2 defines the Lipschitz constant L_D for the divergence D, but Theorem 7.6 and Lemma 7.2 use the notation L_1 without defining its relation to L_D. These symbols should be reconciled.","section":"Section 5 and Theorem 7.6"},{"comment":"In the proof of Lemma B.2, after summing the harmonic-like bound the text writes '≤ Cd + 4√(r_T T)', but the intermediate expression has a factor √d; the correct term should be 4√(r_T d T), matching the statement of the lemma. This appears to be a typographical slip rather than a substantive issue.","section":"Appendix B, proof of Lemma B.2"}],"recommendation":"reject","confidential_remarks":"The paper's scope and ambition are appropriate for a good machine-learning journal, and the generalized eluder dimension idea is worth pursuing. However, the main regret bound in Theorem 7.6 is not established because the decisive application of Lemma B.2 is invalid as written and drops the r_T factor, and the feasibility guarantee is contradicted by the warm-up phase. These are not presentation issues: the advertised central results would need to be restated and re-proved. I would be willing to look at a substantially revised version that fixes the α_r-term analysis and the warm-up feasibility statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper is worth reading for its framework and for the generalized eluder dimension, but the central regret bound is not established by the provided proof, and one of the oracle examples has a scaling error.\n\nThe genuinely new part is the unified formulation of stage-wise constrained contextual decision-making, together with a generalized eluder dimension for density model classes under metric-like divergences. That extension of Russo and Van Roy is natural and probably useful, and the GED-UCB algorithm's reduction to an offline density estimation oracle is in line with current practice. The applications to constrained bandits, active learning, hypothesis testing, and calibration are well motivated, and the writing is clear.\n\nThe soft spots are load-bearing, not cosmetic. In the proof of Theorem 7.6, the decisive step applies Lemma B.2, which bounds the sum of realized-pair divergence amplitudes, to a sum of expected policy-level constraint widths. Those are different objects: the policy-level term is an expectation over a fresh context of a max over actions under the stochastic policy, and no argument bridges the gap. The stated bound also drops the sqrt(r_T) factor that Lemma B.2 carries. So the alpha_r term in the regret is simply unproven.\n\nTheorem 9.1 has a separate scaling problem. For Gaussian densities with known variance sigma^2, the squared Hellinger distance between two means scales as ||Delta||^2 / sigma^2, so the cumulative Hellinger error should be O(d + log(1/delta)) with no sigma^2 factor in front. The paper states a bound of sigma^2 * O(d + ...), which goes to zero as sigma -> 0 and cannot be right for finite samples. This is not a minor typo; it makes the oracle guarantee vacuous in the low-noise regime.\n\nThe generalized eluder dimension lemmas and the framework appear solid, and the flaws may be repairable. But as written, the main theorem is not proven, and the oracle bound is incorrect. The paper deserves a serious referee, because the conceptual contribution is real and the errors are identifiable and fixable. I would send it to review with a clear request: correct the proof of Theorem 7.6 and fix Theorem 9.1's scaling, then re-evaluate.","headline":"A genuinely useful framework and a plausible new complexity measure, but the main regret theorem is not proven as written and the Gaussian oracle bound is dimensionally wrong.","tokens_in":35605,"tokens_out":3368,"would_cite":true,"duration_ms":34987,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single unified algorithm, GED-UCB, solves constrained online decision-making problems ranging from safe bandits to calibration, with regret controlled by a generalized eluder dimension.","keywords":["constrained online decision-making","generalized eluder dimension","upper counterfactual confidence bounds","offline density estimation oracle","utility regret","feasibility constraints","contextual bandits","active learning"],"falsifier":"Construct a constraint density class with a small generalized eluder dimension and an oracle satisfying the assumed cumulative squared-divergence bound, then run Algorithm 1 and measure the cumulative worst-case $T_2$-width $\\sum_t \\max_{g',g''\\in\\tilde{\\mathcal{C}}_G(t,\\delta)}(\\tilde{T}_2(g'_{x_t},\\pi_t)-\\tilde{T}_2(g''_{x_t},\\pi_t))$; if this sum exceeds $\\min\\{T,\\dim_E(\\mathcal{G},D,1/T^2)\\}+4\\sqrt{\\dim_E(\\mathcal{G},D,1/T^2)T}$ by more than a constant, the stated regret bound does not follow.","tokens_in":110,"feed_emoji":"🎯","tokens_out":9569,"duration_ms":115354,"temperature":0.7,"pith_summary":"This paper tries to establish that a wide family of sequential decision problems with per-round feasibility constraints—constrained contextual bandits, stream-based active learning with label budgets, online hypothesis testing with Type I error control, and sequential $L^1$ model calibration—share a single structure and can be solved by one algorithm. The algorithm, GED-UCB, wraps any offline density-estimation oracle into an online policy that is feasible with high probability, and its expected utility regret is controlled by a new complexity measure called the generalized eluder dimension. A sympathetic reader would take the contribution to be a modular reduction: once a density class and an offline estimator are given, the remaining problem of exploration under feasibility constraints is quantified by the divergence-based eluder dimension.","feed_headline":"A generalized eluder dimension governs constrained online regret","feed_subtitle":"GED-UCB turns any offline density estimator into policies that respect stage-wise constraints with high probability.","key_machinery":"The load-bearing object is the generalized eluder dimension $\\dim_E(\\mathcal{G},D,\\varepsilon)$: a context-action pair is $\\varepsilon$-dependent on a history if every two densities in the class that agree on the history up to squared divergence $\\varepsilon^2$ also agree at the new pair, and the dimension is the length of the longest sequence in which each pair is $\\varepsilon'$-independent of its predecessors for some $\\varepsilon'\\ge\\varepsilon$. This definition extends the classical eluder dimension, which was stated for reward functions under squared loss, to any metric-like probability divergence such as total variation, Hellinger, or $L^p$ distance. The algorithm's selection rule combines an upper counterfactual confidence bound with a potential-based exploration bonus and a worst-case constraint-width term $\\max_{g',g''\\in\\tilde{\\mathcal{C}}_G(t,\\delta)}(\\tilde{T}_2(g'_{x_t},\\pi)-\\tilde{T}_2(g''_{x_t},\\pi))$; Lemma B.2 uses the eluder dimension to bound the cumulative size of that width term, which is the step that converts the oracle's estimation error into the feasibility component of the regret bound.","core_discovery":"On its own terms, the paper claims that the constrained per-context decision problem—maximize expected utility $\\tilde{T}_1(f^*_{x_t},\\pi)$ subject to $\\tilde{T}_2(g^*_{x_t},\\pi)\\le\\tau$ at every round—can be solved by a UCB-style algorithm that scores each policy by an estimated utility, a counterfactual exploration bonus, and a constraint-uncertainty penalty. Theorem 7.6 is the central quantitative claim: with probability at least $1-\\delta$, Algorithm 1 selects feasible policies for every round and incurs expected utility regret bounded by $O(2\\beta_T(K+\\log(T/K))+2K\\beta_T\\log T+\\alpha_r(1/T+C\\min\\{T,\\dim_E(\\mathcal{G},D,1/T^2)\\}+4\\sqrt{\\dim_E(\\mathcal{G},D,1/T^2)\\,T}))$, with $\\beta_t$ set from the offline oracle's estimation error and $\\alpha_r=(1-r_0)/(\\tau-c_0)$. In other words, the cost of maintaining feasibility is governed by the generalized eluder dimension of the constraint density class rather than by the context space, and any offline density estimator with a known cumulative squared-divergence bound becomes an online algorithm with a regret guarantee.","pith_inferences":["If the framework's reduction is tight, then the hard part of safe online learning is not algorithm design but bounding a divergence-based eluder dimension; this suggests a research program of computing that dimension for realistic model classes such as neural density estimators.","A natural testable extension is to replace the high-probability feasibility guarantee with an expected violation bound; the same machinery might give smaller regret when occasional small violations are tolerated.","The proof's policy-level width step—controlling the worst-case $T_2$-width of the chosen stochastic policy by the eluder dimension of the realized sequence—is the place where the stated theorem could be strengthened or, if it cannot be proven, the bound would need an additional complexity term.","The same generalized eluder dimension could likely be applied to constrained Markov decision processes and partially observable constrained settings, though the paper only lists those as future work."],"forward_implications":["Every problem that fits the framework—constrained contextual bandits, active learning with a query budget, online hypothesis testing, and $L^1$ calibration—inherits the same per-round feasibility guarantee and same regret decomposition, so results for one application transfer to the others.","The regret bound does not depend on the cardinality of the context space, only on the action count and the generalized eluder dimension of the density class, which is what makes the framework usable for continuous or high-dimensional contexts.","Because the algorithm is built on a black-box offline density estimator, any future estimator with a proven cumulative squared-divergence bound immediately yields a new constrained online algorithm without re-deriving the exploration analysis.","For the concrete classes studied—linear density models under $L^2$ distance, Gaussian families under Hellinger distance, and exponential families under Hellinger distance—the bounds on the generalized eluder dimension give explicit rates, showing the feasibility-related regret grows like $\\sqrt{\\dim_E T}$ up to logarithmic factors.","The setting where the density classes are parameterized subsets of $\\mathbb{R}^d$ and the divergence is Lipschitz in the parameters is covered by a corollary with essentially the same regret, so the finite-class theorem extends to infinite parametric families."],"supporting_citations":[{"why":"Defines the original eluder dimension and optimistic-exploration bound that Definition 5.5 generalizes.","marker":"Russo and Van Roy (2013)"},{"why":"Introduces the upper counterfactual confidence bound principle that underlies the algorithm's policy scoring.","marker":"Xu and Zeevi (2020)"},{"why":"Supplies the interactive-decision-making complexity framework and a concentration inequality used in the regret proof.","marker":"Foster et al. (2021)"},{"why":"Provides a stage-wise constrained linear bandit baseline and safe-action assumption that the framework generalizes.","marker":"Pacchiano et al. (2021)"},{"why":"Uses eluder dimension for conservative exploration under unknown constraints, the line of analysis the paper extends.","marker":"Sridharan and Yoo (2024)"},{"why":"Formulates the neural active-learning problem with budget constraints that Section 4.2 instantiates as a special case.","marker":"Awasthi et al. (2021)"}],"fun_headline_variants":["Constrained regret governed by generalized eluder dimension","Unified framework tames constraints in online decisions","Feasibility regret scales with generalized eluder dimension","Any density oracle becomes a safe online learner","Constrained decisions with bounded regret via GED-UCB"],"cache_read_input_tokens":37632,"weakest_assumption_plain":"The load-bearing premise is that the worst-case constraint uncertainty of the stochastic policy chosen at each round is controlled by the generalized eluder dimension of the realized context-action sequence; the proof of Theorem 7.6 assumes this policy-level control rather than deriving it.","fun_headline_variants_meta":{"raw":{"variants":["Constrained regret governed by generalized eluder dimension","Unified framework tames constraints in online decisions","Feasibility regret scales with generalized eluder dimension","Any density oracle becomes a safe online learner","Constrained decisions with bounded regret via GED-UCB"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000503,"raw_usage":{"total_tokens":2492,"prompt_tokens":1017,"completion_tokens":1475,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":1399}},"tokens_in":633,"tokens_out":1475,"duration_ms":12213,"temperature":1.0,"reasoning_tokens":1399,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:25:34.394232+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a constraint density class with a small generalized eluder dimension and an oracle satisfying the assumed cumulative squared-divergence bound, then run Algorithm 1 and measure the cumulative worst-case $T_2$-width $\\sum_t \\max_{g',g''\\in\\tilde{\\mathcal{C}}_G(t,\\delta)}(\\tilde{T}_2(g'_{x_t},\\pi_t)-\\tilde{T}_2(g''_{x_t},\\pi_t))$; if this sum exceeds $\\min\\{T,\\dim_E(\\mathcal{G},D,1/T^2)\\}+4\\sqrt{\\dim_E(\\mathcal{G},D,1/T^2)T}$ by more than a constant, the stated regret bound does not follow.","supporting_citations":[{"cited_title":"Stochastic bandits with linear constraints","cited_arxiv_id":null,"evidence_quote":"Provides a stage-wise constrained linear bandit baseline and safe-action assumption that the framework generalizes."},{"cited_title":"Online Learning with Unknown Constraints","cited_arxiv_id":"2403.04033","evidence_quote":"Uses eluder dimension for conservative exploration under unknown constraints, the line of analysis the paper extends."}],"review_version":1}