{"id":"b85d1ec9-7445-49be-ad4f-b5386033ea04","arxiv_id":"2608.07922","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For W at least C_d log(eT), minimax pseudo-regret in Lipschitz bandits is, up to logarithmic factors, the maximum of the sequential rate, a new memory-batch penalty T^((d+2)/(d+3)) (1+(B-1)W)^(-1/(d(d+3))), and a batch-depth term.","lead":"An information-theoretic analysis identifies the exact regret cost of combining a W-bit memory with B committed action batches in stochastic Lipschitz bandits. It shows memory width and batch depth are complements, not substitutes, and gives a single frontier that recovers both classical sequential and batched-only rates.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower bound's entropy bottleneck is sound but rests entirely on the no-external-transcript interface; the unqualified static-versus-adaptive claim should be restricted to W≳log(eT).","rationale":"The paper's central theorem is a genuine joint characterization: the fixed-scale envelope, the boundary-state entropy budget, and the regional hard family fit together coherently, and I found no fatal mathematical error in the main information-routing argument. The reader's weakest-assumption identification is accurate: the bound I(V;T|F0)≤χ is the pivot of the lower bound, and it holds only because the model forbids reward-dependent storage outside the W-bit state. This is an explicit modeling convention rather than an internal inconsistency, so it does not justify rejection. The secondary overclaim is the unqualified statement that predictable adaptive boundaries do not improve over static ones; the theorem's static upper bound is proved only in the W≥C_d log(eT) regime, and the sublogarithmic regime is left open. That supports the reader's conditional acceptance with a requested qualification. No code or formal verification is provided, and the lower bound for the B-dependent branch relies on a transfer from Feng et al. (2024), so moderate confidence with a conditional verdict is appropriate.","tokens_in":35191,"tokens_out":34844,"duration_ms":415434,"concrete_test":"Re-derive Lemmas 3.2 and 3.3 with a Q-bit external reward-dependent transcript or hidden registers, and recompute the regional-routing lower bound. If the entropy budget becomes (B−1)W+Q and the interaction penalty becomes T^{(d+2)/(d+3)}(1+(B−1)W+Q)^{-1/(d(d+3))}, the no-external-storage convention is confirmed as the load-bearing premise. Then check whether Q=O(1) suffices for a policy to violate the original lower bound; if not, the convention is benign in that regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound is driven by Lemmas 3.2 and 3.3: conditional on F0, the committed transcript T is a deterministic function of the tuple M of boundary states, so I(V;T|F0)≤H(M|F0)≤(B−1)W. This is exactly where the no-uncharged-storage convention is load-bearing. If a learner could keep reward-dependent information in hidden registers, an external transcript, or reward-dependent stopping/round counts outside the W-bit state, the reconstruction map would not have range at most 2^χ, and the routing lower bound (Lemma 4.3) and codebook bound (Proposition 4.4) would not follow. The paper states this convention explicitly ('There is no separate persistent reward-dependent workspace or accumulating external transcript'), so the theorem is internally consistent; however, the tradeoff is defined by that modeling choice, and a relaxation with Q uncharged bits would change the budget to χ+Q and the interaction term to (1+(B−1)W+Q)^{-1/(d(d+3))}. Separately, the Section 1 statement 'Predictable adaptive boundaries do not improve the worst-case order over static ones' is proved only for W≥C_d log(eT); the sublogarithmic regime is declared open, so this claim should be qualified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies a joint resource model for stochastic Lipschitz bandits on [0,1]^d: after each pull the learner may retain at most W bits of live reward-dependent state, and its pulls are organized into at most B committed batches whose boundaries and action tapes are fixed at batch boundaries. The main result, Theorem 3.4, gives a two-sided minimax characterization up to logarithmic factors when W is at least a dimension-dependent constant times log(eT), with a lower bound valid for every W. The regret frontier is the maximum of three terms: the classical sequential term T^{alpha_d}, a batch-depth term T^{beta_{d,B}}/B^2, and a new interaction penalty T^{(d+2)/(d+3)}(1+(B-1)W)^{-1/(d(d+3))}. The lower bound is proved through a regional hard family in which low regret forces the committed action transcript to encode many regional routing decisions, while the boundary states carry at most (B-1)W bits of entropy; a separate adaptive-grid argument supplies the batch-depth branch. The upper bound maintains only a safe active-set mask, either in memory or in regenerated fragments, while streaming and erasing verification statistics. Corollaries recover the unrestricted-memory batched frontier and the fully sequential logarithmic-memory specialization, and static batch boundaries are shown to match predictable adaptive ones in the characterized regime.","tokens_in":35444,"tokens_out":17673,"duration_ms":205168,"significance":"If the result is correct, it is a substantive contribution to the theory of resource-constrained bandits. The paper identifies a genuinely new interaction term coupling state width W and batch depth B, and it proves that the two resources are not interchangeable, which is the paper's central conceptual claim. The lower and upper bounds are matched up to logarithmic factors, the theorem cleanly specializes to the previously known batch-only and fully sequential finite-memory frontiers, and the appendices give a detailed, largely self-contained accounting of the geometry, the information-theoretic boundary-state argument, and the streaming algorithms. The model is carefully defined, including the crucial convention that there is no uncharged reward-dependent workspace or accumulating external transcript; this convention is load-bearing for the lower bound, but it is stated explicitly rather than hidden. The main limitations are the logarithmic gaps, the restriction of the matching upper bound to W >= C_d log(eT), and the fact that the sublogarithmic regime is left open.","major_comments":[],"minor_comments":[{"comment":"The model description should be tightened around the status of the committed action tape. The text first says there is no separate persistent reward-dependent workspace or accumulating external transcript, but then allows a fixed read-only action tape that replays information already encoded in the preceding W-bit boundary state. Appendix A.1's formal map-level definition has no tape variable, yet the upper-bound memory accounting in Proposition 5.3 and Appendix D implicitly treats the committed tape as free. Please state explicitly that W is the read-write workspace, while the committed tape is an uncounted read-only output determined by the boundary state; this would remove an apparent contradiction and make the lower-bound convention unambiguous.","section":"Section 3.1 and Appendix A.1"},{"comment":"The statements 'Predictable adaptive boundaries do not improve the worst-case order over static ones' are proved only in the regime W >= C_d log(eT), since the matching static upper bound in Theorem 3.4 has exactly that hypothesis and the sublogarithmic regime is declared open in Section 6. Please qualify these claims by adding 'for W >= C_d log(eT)' or by placing them explicitly under the theorem's stated condition.","section":"Sections 1 and 2"},{"comment":"In the d=1 specialization, the condition for near-sequential regret is stated as 'chi >= T^{1/3}', but the exact condition derived from the (1+chi)^{-1/(d(d+3))} term is (1+chi) >= c T^{1/3}. Consider writing '1+chi >= T^{1/3}' (with a dimension constant) to match Eq. (3) exactly.","section":"Remark 3.5"},{"comment":"The displayed lower bound in Eq. (6) contains a factor of ell_T^{-d(d+3)}, while the upper bound has no ell_T factor. Since Eq. (7) then suppresses logarithmic factors, it would be helpful to add a sentence stating explicitly that Eq. (6) does not track logarithmic factors, or to include the exact log exponents in both bounds so the displayed asymmetry is intentional.","section":"Corollary 3.8 and Appendix F"},{"comment":"In Lemma 3.3, the Markov chain V -> M -> T -> R is stated conditionally on F0. The independence of the decoder randomization from the experiment makes the final step valid, but a one-sentence reminder after the lemma would help readers see why R is conditionally independent of V given T rather than merely generated in a complicated way from the transcript.","section":"Section 3.2"}],"recommendation":"minor_revision","confidential_remarks":"This is a strong theory paper whose central characterization appears sound and whose proofs are unusually detailed. My main hesitation is the modeling convention that committed action tapes are free and uncounted while W measures only mutable state; this convention is stated, but it deserves to be foregrounded because the lower bound's entropy budget and the upper bound's memory guarantees both depend on it. If the editor prefers that the paper address models with uncharged storage more broadly, the authors should be asked to add a discussion rather than to change the theorem. I would not require major revision for this; a revision with the clarifications listed in the minor comments would be sufficient."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is right: the paper proves a real joint minimax frontier for stochastic Lipschitz bandits under simultaneous W-bit state and B-batch constraints. The new interaction penalty T^{(d+2)/(d+3)}(1+(B-1)W)^{-1/(d(d+3))} is genuinely new, and it shows width and depth are not substitutes. The core idea—boundary states carry at most (B-1)W bits of entropy, while a low-regret transcript must encode Theta(s^{-d}) regional decisions—is clean and well executed. The regional hard family that yields both the statistical and memory terms is elegant. The upper bound is also careful: active-set masks, streaming/erasing verification stats, and exact batch and memory accounting appear in the appendices. I found no fatal mathematical error in the main argument.\n\nThe soft spots are proportionate. The lower bound rests on the model's no-uncharged-storage interface: no hidden registers, no accumulating external transcript. The paper states this explicitly, so the result is internally consistent, but it is a statement about that interface, not about every physical realization. If you relax it with Q uncharged bits, the interaction term becomes (1+(B-1)W+Q)^{-1/(d(d+3))}. That deserves a sentence in the paper, not a rejection.\n\nThe other issue is the static-vs-adaptive claim. The abstract and intro say static batch boundaries match adaptive ones without qualification. The upper bound that achieves this is proved only for W >= C_d log(eT); the sublogarithmic regime is declared open. So the claim should be qualified to the regime where the upper bound holds. Minor, but the current phrasing overreaches.\n\nThe batch-depth branch imports the adaptive-grid lower bound from Feng et al. (2024) and transfers it to Bernoulli rewards. The transfer looks correct from the appendix, but it is an external dependency; a referee should check Lemma B.7 carefully. No code or formal proofs, but that is normal for this literature.\n\nThis is for anyone working on resource-constrained adaptive learning, streaming bandits, or batched feedback with memory limits. It is a substantial organizational step and deserves a serious referee. My recommendation: send it out; the needed fixes are minor qualifications, not structural changes.","headline":"A genuine joint memory-batch frontier for Lipschitz bandits, with a clean information-routing lower bound and careful matching constructions, but the model's no-uncharged-storage assumption and an overbroad static-vs-adaptive claim need qualification.","tokens_in":35982,"tokens_out":2750,"would_cite":true,"duration_ms":30642,"reading_group":"yes","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 a near-tight minimax regret characterization for stochastic Lipschitz bandits with $W$-bit live memory and $B$ committed batches, introducing the joint penalty $T^{(d+2)/(d+3)}(1+(B-1)W)^{-1/(d(d+3))}$.","keywords":["Lipschitz bandits","minimax regret","finite-memory bandits","batched bandits","information routing","boundary-state entropy","active-set mask","committed batches"],"falsifier":"Simulate the $d=1$ hard family with $B=2$ and $W=0$ over horizons $T=10^2,\\dots,10^6$: the theorem says the best 0-bit 2-batch policy has linear regret, so any schedule whose normalized regret decays with $T$ would refute the lower bound.","tokens_in":34989,"feed_emoji":"🎰","tokens_out":15917,"duration_ms":146889,"temperature":0.7,"pith_summary":"Adaptive learning needs both room to store what rewards imply and chances to act on that stored information. The paper proves that in stochastic Lipschitz bandits, a learner with at most $W$ bits of live reward-dependent state and at most $B$ committed batches suffers minimax expected pseudo-regret that, once $W \\gtrsim_d \\log(eT)$, is determined up to logarithmic factors by the worst of three terms: the classical sequential floor, the unrestricted-memory batch floor, and a new interaction involving $(B-1)W$. Lower bounds hold for every $W$, so the interaction is not confined to the memory-rich regime. The proof shows the interaction is an information-routing constraint: low regret forces the committed action transcript to encode a growing number of regional decisions, while the boundary states that can influence later experiments carry at most $(B-1)W$ bits in total. This matters because it says memory width and update depth are complementary resources, not substitutes: one wide state used by very few redesigns cannot replace a sequence of narrow states recomputed between rounds of exploration.","feed_headline":"Width can't replace depth in Lipschitz bandits","feed_subtitle":"New minimax bounds tie regret to the product (B-1)W of boundary-state bits and batch count.","key_machinery":"The carrying object is the boundary-state entropy budget $\\chi=(B-1)W$. Lemma 3.2 shows that, conditional on the public seed, every reward-dependent element of the committed action transcript is a measurable function of the tuple of nonterminal boundary states, so for any latent instance variable $V$ the information profile satisfies $I(V;\\mathcal{T}\\mid F_0) \\le H(M\\mid F_0) \\le \\chi$. Against this budget, the hard family places $m \\asymp_d s^{-d}$ separated pairs of scale-$s$ regions with $q \\asymp_d (s/r)^d$ radius-$r$ probes per region; a stopped change-of-measure argument forces any low-regret transcript to encode $\\Theta_d(s^{-d})$ regional decisions, and Fano decoding then yields the resolution floor $s_{\\mathrm{mem}}=(1+\\chi)^{-1/d}$. The upper bound is a safe active-set mask of the same spatial order, maintained either entirely in memory or as regenerated one-memory-sized fragments, while all fine verification statistics are accumulated, compared, and erased.","core_discovery":"The central claim is Theorem 3.4: for $d \\ge 1$, $T \\ge T_d$, $B \\in [T]$, and $W \\ge 0$, the minimax expected pseudo-regret satisfies $R_T(B,W) \\ge c_d [\\Psi_T(s_{T,\\chi}) \\vee T^{\\beta_{d,B}}/B^2]$, and whenever $W \\ge C_d \\log(eT)$ it also satisfies $R_T(B,W) \\le C_d \\log(eT)[\\Psi_T(s_{T,\\chi}) \\vee T^{\\beta_{d,B}}/B^2]$, with $\\alpha_d=(d+1)/(d+2)$, $\\beta_{d,B}=\\alpha_d/(1-(d+2)^{-B})$, $\\chi=(B-1)W$, and $s_{T,\\chi}=\\max\\{T^{-1/(d+2)}, (1+\\chi)^{-1/d}\\}$, where $\\Psi_T(s)=T^{(d+2)/(d+3)}s^{1/(d+3)}$. Explicitly, the frontier is the maximum of $T^{\\alpha_d}$, $T^{\\beta_{d,B}}/B^2$, and the new interaction $T^{(d+2)/(d+3)}(1+(B-1)W)^{-1/(d(d+3))}$. The same regional hard family produces the sequential and interaction terms, and an adaptive-grid transfer produces the update-depth term; matching policies use static batch boundaries and retain only an active-set mask while streaming and erasing verification statistics. Thus the result recovers the batch-only frontier with unrestricted memory and the fully sequential minimax rate with logarithmic live memory as specializations.","pith_inferences":["Beyond the paper's terminal regret bounds, the prefix profile $I(V;\\mathcal{T}[j]\\mid F_0) \\le (j-1)W$ suggests a time-resolved converse: the same Markov factorization should yield per-batch regret lower bounds, not just an end-of-horizon statement.","The mechanism is likely to transfer to other nonparametric classes where the number of relevant regions grows with resolution: the effective dimension in the memory floor may become the zooming or near-optimality dimension of the class, not the ambient dimension.","The serialized active-set construction is a concrete streaming template: regenerate a memory-sized mask fragment, commit the corresponding child probes, update one resident best record, and erase the fragment; the same pattern could be exported to memory-bounded hierarchical optimization on devices with no random-access storage.","A natural testable next step is the sublogarithmic regime $W<\\log(eT)$: the very-low-entropy codebook bound $R_T(B,W) \\ge c_d T2^{-\\chi/d}$ suggests an exponential-in-$\\chi$ frontier there, but the paper leaves this regime open."],"forward_implications":["Once $W \\ge C_d \\log(eT)$, the joint memory–batch minimax regret is characterized up to logarithmic factors, and static batch boundaries achieve the worst-case optimal order.","Near-sequential regret requires both $B \\gtrsim \\log\\log T$ and $(B-1)W \\gtrsim T^{d/(d+2)}$; the batch complexity is $\\widetilde{\\Theta}_d(\\log\\log T \\vee T^{d/(d+2)}/W)$.","With unrestricted memory, the theorem recovers the full-dimensional batch-only frontier $T^{\\alpha_d} \\vee T^{\\beta_{d,B}}/B^2$ for every batch budget $B$.","With $B=T$, the model is fully sequential and the theorem recovers the classical minimax regret $\\widetilde{\\Theta}_d(T^{(d+1)/(d+2)})$ using only logarithmic live memory.","The new interaction penalty shows concretely that state width and update depth are not interchangeable: concentrating the same boundary-state entropy into fewer, wider states cannot reproduce the sequence of refinements needed."],"supporting_citations":[{"why":"Establishes the classical continuum-armed bandit minimax rate that the sequential branch of the frontier recovers.","marker":"Agrawal (1995)"},{"why":"Gives the near-tight sequential continuum-armed bandit bound used as the statistical baseline.","marker":"Kleinberg (2004)"},{"why":"Provides improved stochastic continuum-armed bandit rates that feed the classical sequential term.","marker":"Auer et al. (2007)"},{"why":"Supplies the metric-space X-armed bandit framework used for the smoothness assumptions of the hard family and upper bound.","marker":"Bubeck et al. (2011)"},{"why":"Supplies the adaptive-grid lower bound and the BLiN construction that produce the update-depth term $T^{\\beta_{d,B}}/B^2$ and the batch-only frontier.","marker":"Feng et al. (2024)"},{"why":"Introduces the persistent-state/committed-batch interface and the stopped change-of-measure argument adapted to the regional hard family.","marker":"Huang et al. (2026)"},{"why":"Proves logarithmic live memory is sufficient and necessary for sequential Lipschitz bandits, a result recovered by the $B=T$ specialization.","marker":"Zhu and Huang (2025)"},{"why":"Provides the entropy and Fano machinery behind the transcript codebook and decoding lower bounds.","marker":"Cover and Thomas (2006)"}],"fun_headline_variants":["Width can't buy depth in bandit regret","New regret penalty couples memory and batch count","Bandit frontier shows memory and batches aren't swappable","Tight bounds: (B-1)W bits drive regret tradeoff","Lipschitz bandits: width and depth both cost regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound rests on the assumption that the declared $W$-bit state is the only reward-dependent storage, with all randomness and schedules fixed by the public seed; if reward-dependent information can persist outside that state—in hidden registers, external transcripts, or reward-dependent timing not captured by the state—the entropy budget $(B-1)W$ and the entire routing lower bound would no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Width can't buy depth in bandit regret","New regret penalty couples memory and batch count","Bandit frontier shows memory and batches aren't swappable","Tight bounds: (B-1)W bits drive regret tradeoff","Lipschitz bandits: width and depth both cost regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000736,"raw_usage":{"total_tokens":3395,"prompt_tokens":1156,"completion_tokens":2239,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":772,"completion_tokens_details":{"reasoning_tokens":2156}},"tokens_in":772,"tokens_out":2239,"duration_ms":18543,"temperature":1.0,"reasoning_tokens":2156,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:42:12.319777+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the $d=1$ hard family with $B=2$ and $W=0$ over horizons $T=10^2,\\dots,10^6$: the theorem says the best 0-bit 2-batch policy has linear regret, so any schedule whose normalized regret decays with $T$ would refute the lower bound.","supporting_citations":[],"review_version":1}