{"id":"f1d0fe89-d013-452c-92bf-d9bf6c24ae20","arxiv_id":"2607.20636","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For improving multi-armed bandits, randomized algorithms achieve a near-tight Θ~(√k) worst-case competitive ratio, and polynomially many historical instances suffice to tune a curvature parameter; pessimism traps and grit are modeled as sequential decision problems.","lead":"This PhD thesis proves near-optimal worst-case guarantees for improving multi-armed bandits and develops formal models of pessimism traps and grit, including financial interventions. Read it to see how far abstraction can go in explaining when people persist, give up, or get influenced by their predecessors.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Sample-complexity proof undercounts algorithm behaviors; Q_D ≤ kT does not follow as written, though it is likely repairable via monotonicity.","rationale":"I read Part I as the technical core. The worst-case lower bound survives scrutiny: the 'universe' game is strictly more generous to the algorithm, and the event analysis gives expected reward ≤ O(OPT/√k). The upper-bound recurrence solves correctly up to inessential constants. The place where the text actually breaks is the data-driven sample-complexity proof: Lemma 4.3.3's counting step is false as written, and this is the exact support for Theorem 4.3.4. However, the false step is not load-bearing in the sense of making the theorem false: a monotonicity argument supplies the kT bound, so a corrected proof should restore the stated sample complexity. I therefore would not reject, but the thesis should be accepted conditionally on repairing this proof (and the analogous Lemma 4.4.2) and on adding the rational-agent caveat to abstract-level social claims. The reader's primary weakest assumption was the rational-agent idealization; I agree that is a real scope limitation, but it is explicitly acknowledged in §5.1.4 and is part of the thesis's stated modeling philosophy, so it is less of a correctness risk than the unproven counting claim. The absent LCDB code is a reproducibility issue, not a mathematical one. Overall the reader's CONDITIONAL verdict is right; my stress-test does not move it.","tokens_in":51625,"tokens_out":20544,"duration_ms":160611,"concrete_test":"For a fixed augmented instance/permutation, write the dual loss ℓ(α) for PTRR_α and count its breakpoints. Use the fact that a stop time changes only when m(t/τ)^α = f_i(t) for some (i, t), giving at most kT candidate α values; verify the number of distinct loss values is ≤ kT + 1. If true, Theorem 4.3.4 stands as stated after replacing the tuple-counting argument with a breakpoint/monotonicity argument. Independently repeat for Hybrid α,B in Lemma 4.4.2, expecting at most kT^2 breakpoints. If the counts exceed these, revise Theorem 4.3.4/4.4.3 and the abstract's sample-complexity claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Lemma 4.3.3 says the tuple R_α = (t_stop^(1), ..., t_stop^(k)) has at most kT possible values because each coordinate has T values. That counting is wrong: the Cartesian product has T^k values. As written, Q_D ≤ kT is unsupported, and Theorem 4.3.4's O((H/ε)^2(log kT + log 1/δ)) bound does not follow. Lemma 4.4.2 (Q_D ≤ kT^2) has the same gap. The bound is almost certainly salvageable: for a fixed derandomized instance, each t_stop^(j) is monotone nondecreasing in α because the threshold m(t/τ)^α decreases with α, so the set of tuples visited across α is a monotone path with at most kT distinct values. But that argument is not in the text; as submitted the proof is incomplete. If the correct bound is instead T^k, the sample complexity becomes O((H/ε)^2(k log T + log 1/δ)) — still polynomial, so the 'polynomially many samples' slogan survives, but the stated logarithmic dependence is wrong.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The thesis studies sequential decision-making and social epistemology around the common theme of choosing whether to persist or give up. Part I addresses the improving multi-armed bandits (IMAB) problem. Chapter 3 gives a worst-case Yao lower bound of Ω(√k) on the approximation factor of any randomized algorithm and an O(√k log k) upper bound via a randomized round-robin algorithm whose analysis is based on a checkable recurrence. Chapter 4 moves to the data-driven algorithm design framework: it introduces a one-parameter family PTRR_α, proves sharper competitive ratios depending on a concavity-envelope exponent β, claims sample-complexity bounds for tuning α, and proposes a two-stage hybrid family for best-arm identification with best-of-both-worlds guarantees. Part II contains a philosophical chapter on the roles of theoretical models, followed by models of pessimism traps with time-varying financial subsidies and a formal treatment of grit as optimism or discomfort tolerance. The manuscript is a thesis-style compilation of several conference papers, with Chapter 5 newly written.","tokens_in":51930,"tokens_out":8074,"duration_ms":67707,"significance":"If the results hold, the thesis makes solid contributions: the worst-case IMAB bounds are nearly tight and improve on the deterministic Θ(k) result; the β-dependent competitive ratios are a natural and useful refinement; and the data-driven framework is a reasonable route beyond worst-case analysis. The empirical study on LCDB learning curves is a welcome addition, even though the differences across α are modest for most datasets. The Part II models are more interpretive, but the thesis is unusually candid about their limitations—especially the rational-agent idealization flagged in Section 5.1.4—which is a genuine strength. The main technical concern is in the sample-complexity analysis of Chapter 4, where a counting argument is incorrect as written.","major_comments":[{"comment":"The proof of Lemma 4.3.3 counts the tuple R_α = (t_stop^(1), ..., t_stop^(k)) as having at most kT possible values because each coordinate takes one of T values. The Cartesian product has T^k values, not kT, so the asserted bound Q_D ≤ kT is not established by the written argument. Consequently, Theorem 4.3.4's bound O((H/ε)^2(log kT + log(1/δ))) does not follow. The same flaw appears in Lemma 4.4.2, where Q_D ≤ kT^2 is asserted for the two-parameter hybrid family. The bound is likely salvageable: for a fixed derandomized instance, each t_stop^(j) is monotone in α, so the set of tuples visited lies on a monotone path with at most O(kT) distinct points; but that argument is not present. If the product bound T^k is used instead, the sample complexity becomes O((H/ε)^2(k log T + log(1/δ))), which is still polynomial but changes the stated logarithmic dependence. This is load-bearing for the","section":"§4.3.3, Lemma 4.3.3 and §4.4.3, Lemma 4.4.2"}],"minor_comments":[{"comment":"The displayed expression bounding the reward under event E^c is garbled and does not parse to the claimed T/k + T/√k − T/k. It should be the sum over the triangular reward of a suboptimal arm, e.g. sum_{t=1}^{T/√k} t/T + (T − T/√k)/√k. The final bound is still recoverable, but the equation needs rewriting.","section":"§3.2, proof of Theorem 3.2.1"},{"comment":"The row for [HKR16] says 'sublinear as T→0'; this should presumably read 'as T→∞'.","section":"§2.3, Table 2.1"},{"comment":"The lemma is stated for 'the family B defined in Defn. 4.3.1', but it concerns the hybrid family Hybrid from Definition 4.4.1. Please correct the cross-reference.","section":"§4.4.3, Lemma 4.4.2"},{"comment":"Algorithm 1 uses a strict inequality 'f_i(t_i) > m t_i/T' to continue, whereas Algorithm 4 uses '≥'. This is immaterial to the analysis but should be made consistent or explicitly noted.","section":"Algorithms 1 and 4"},{"comment":"The text says the figure shows that the best α varies across datasets, but the main-text figure is explicitly a selection of datasets, and the caption notes that most differences are within confidence intervals. The full sweeps in Appendix B.3.6 should be summarized in the main text so the claim is directly supported.","section":"§4.3.4, Figure 4.4"},{"comment":"Typo: 'near-optional' should be 'near-optimal'.","section":"§4.3.3"}],"recommendation":"major_revision","confidential_remarks":"The counting error in Lemma 4.3.3 is the main substantive issue. I believe it is repairable, so I recommend major revision rather than rejection. The Part II chapters are more interpretive and may raise scope questions for a cs.DS venue, but the thesis is appropriately self-aware about the limits of the rational-agent idealization."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this thesis is mostly a compilation of four conference papers by the author and collaborators. The genuinely new text is Chapter 5, a reflective essay on what theoretical models can and cannot do for social problems. If you came here expecting new technical results, you won't find them; but if you want a coherent overview of the improving multi-armed bandits results, this is a well-organized document.\n\nWhat is actually good: the worst-case IMAB results from Chapter 3 are rigorous and important. The lower bound via Yao's principle and the matching O(sqrt(k) log k) upper bound are carefully argued. I checked the recurrence and the stopping-time analysis; they hold. The thesis is also unusually honest about provenance and limitations. Section 5.1.4 openly acknowledges that the rational-agent idealization is a simplification and that this makes it harder to assess real-world relevance. That kind of self-awareness is rare and worth crediting.\n\nThe soft spots are real but not fatal. Lemma 4.3.3 claims that the set of stopping-time tuples has size at most kT. That is simply wrong: each coordinate has T possible values, so the product has T^k. The proof as written does not establish the stated O(log kT) sample complexity. The stress-test note is right that a monotonicity argument likely fixes this and still gives polynomial sample complexity, but the text needs to be corrected. The same gap appears in Lemma 4.4.2. This is a proof bug, not a fatal flaw, because the result is probably salvageable.\n\nThe LCDB experiments in Chapter 4 are presented without code or a detailed reproducibility harness. For a theory thesis that's not disqualifying, but it does mean the empirical claims should be read as illustrative. The social-epistemology chapters are formal models with no empirical validation, so treat their conclusions as hypotheses, not findings.\n\nWho is this for? People working on improving bandits or data-driven algorithm design will want to read Chapter 3 and the corrected version of Chapter 4. The essay in Chapter 5 might interest philosophers or computer scientists thinking about model-building.\n\nRecommendation: this deserves a serious referee, not a desk rejection. The referee should focus on fixing Lemma 4.3.3 and verifying the monotonicity repair. I wouldn't cite the thesis itself in the next year because the underlying results are in the conference papers, but I'd definitely engage with the corrected version.","headline":"A solid thesis that repackages four peer-reviewed IMAB papers; the new material is an honest philosophical essay, and the main soft spot is a repairable counting bug in the data-driven sample-complexity proof.","tokens_in":52413,"tokens_out":1458,"would_cite":false,"duration_ms":16292,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68W27","91A26","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This thesis proves no randomized algorithm for improving multi-armed bandits can beat an Ω(√k) approximation factor, then matches it up to a log with a simple threshold rule and extends to data-driven tuning and social models.","keywords":["improving multi-armed bandits","competitive ratio","diminishing returns","data-driven algorithm design","sample complexity","best-arm identification","pessimism traps","grit"],"falsifier":"Take the lower-bound family with one arm rising linearly and k-1 arms flattening after T/√k pulls; if any randomized algorithm achieves a worst-case competitive ratio o(√k) on that family, the central lower bound is false. For the social claim, implement the time-varying subsidy in a cascade experiment with human or simulated agents: if communities return to the pessimistic equilibrium after the subsidy is withdrawn, the sustainability claim fails.","tokens_in":51509,"feed_emoji":"🎯","tokens_out":7239,"duration_ms":53193,"temperature":0.7,"pith_summary":"The thesis asks how a decision-maker should allocate effort among options whose reward grows with investment, in the worst case and when similar historical instances are available. It establishes that in the general improving multi-armed bandits problem, no randomized algorithm can approximate the optimal cumulative reward better than a factor of Ω(√k), and it gives a simple 'play until it can no longer be best, then discard' algorithm that attains O(√k log k) using only an estimate of the best option's final value. With polynomially many past instances, empirical risk minimization over a one-parameter family of algorithms is near-optimal in expectation. In the social half, the thesis provides a formal model of pessimism traps and proves a time-varying subsidy can shift communities out of them permanently, and models grit as optimism or discomfort tolerance.","feed_headline":"The √k limit for improving bandits is tight up to a log","feed_subtitle":"A simple discard rule nearly matches the bound, and historical instances can beat the worst case.","key_machinery":"The central object in Part I is the 'power-thresholded round robin' (PTRR_α), the family of algorithms that pulls an arm only while f_i(t_i) ≥ m (t_i/τ)^α, where m estimates the best arm's final reward and τ is an internal horizon. The α parameter measures the strength of concavity assumed: α=1 is a linear threshold and recovers the √k worst-case algorithm; α<1 exploits the condition that every arm lies above a power lower envelope to improve the competitive ratio to k^{α/(α+1)}. In Part II, the carrying mechanism is a sequential social-learning cascade: each agent chooses an ambitious or modest option based on predecessors' actions and a private signal, and pessimism traps form when modest","core_discovery":"At the heart of the technical half is a sharpening of the worst-case view of improving bandits: even with randomization, the best achievable approximation factor is Θ̃(√k). The lower bound comes from a distribution where a single arm rises linearly while all others flatten after T/√k pulls; the upper bound is a randomized round-robin that keeps an arm only while its observed reward stays above a line from the origin to its estimated final value. The same threshold rule, generalized to a power curve with exponent α, interpolates between the √k worst-case and better guarantees when reward curves are more concave; a matching lower bound shows the exponent is optimal. The thesis then proves that","pith_inferences":["The threshold-rule view suggests a simple, testable design principle for human 'singular evaluation': an agent who discards an option as soon as evidence rules it out is nearly optimal at the scale of the number of options, even without knowing the best option's true value; this could be probed in behavioral experiments by measuring whether people's thresholds approximate a downward-sloping line.","The data-driven sample-complexity bound implies that for any domain with stationary learning curves, an organization can amortize the cost of tuning over repeated deployments, because the number of historical instances needed grows only polynomially in desired accuracy and logarithmically in the horizon and number of options.","The pessimism-trap result suggests a testable policy prediction: a time-limited subsidy that is randomly varied across communities should produce lasting divergence between treated and untreated communities even after the subsidy ends, whereas a fixed subsidy would need to be permanent. This contrast could be checked in field experiments or with quasi-experimental variation.","If grit is optimism or discomfort tolerance, then policies that seed optimism are substitutes for financial support; the thesis's models imply the two levers have different comparative statics, for instance that grit helps most when the true threshold is moderate, which is a prediction about when mentorship versus cash is more effective."],"forward_implications":["For any deployment of improving bandits where rewards are concave and the horizon is finite, the √k bound is the right benchmark: no amount of clever randomization can do better in the worst case, and the threshold algorithm is within a log factor.","If a practitioner has historical learning curves or similar past instances, they need only polynomially many samples—roughly (H/ε)^2 log(kT/δ)—to tune the curvature parameter and the switch time; the tuned algorithm is near-optimal in expectation.","On instances whose reward curves are more concave than linear (satisfying a β-power lower envelope), the PTRR family strictly improves the competitive ratio to k^{β/(β+1)}, with a matching lower bound showing this exponent is the best possible.","Best-arm identification can be made robust: a hybrid algorithm commits to the best arm exactly when a gap-clearance condition holds within the budget, and otherwise returns an arm whose final reward is within a k^{α/(α+1)} factor of the best arm.","In the social model, carefully designed time-varying subsidies can permanently move communities out of pessimism traps, and grit, formalized as optimism or discomfort tolerance, changes when a rational agent abandons an ambitious goal."],"fun_headline_variants":["Tight √k bound for improving bandits","Randomized round-robin hits the √k limit","Data-driven algorithm design: polynomial samples suffice","Pessimism traps: model and financial interventions","Grit in ambitious decisions: theoretical model"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that human decision-makers are rational Bayesian expected-utility maximizers; the thesis itself concedes (Section 5.1.4) that this defines the procedure agents are assumed to follow and makes it harder to judge real-world relevance.","fun_headline_variants_meta":{"raw":{"variants":["Tight √k bound for improving bandits","Randomized round-robin hits the √k limit","Data-driven algorithm design: polynomial samples suffice","Pessimism traps: model and financial interventions","Grit in ambitious decisions: theoretical model"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000491,"raw_usage":{"total_tokens":2290,"prompt_tokens":819,"completion_tokens":1471,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":1400}},"tokens_in":563,"tokens_out":1471,"duration_ms":25427,"temperature":1.0,"reasoning_tokens":1400,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T09:46:46.808566+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the lower-bound family with one arm rising linearly and k-1 arms flattening after T/√k pulls; if any randomized algorithm achieves a worst-case competitive ratio o(√k) on that family, the central lower bound is false. For the social claim, implement the time-varying subsidy in a cascade experiment with human or simulated agents: if communities return to the pessimistic equilibrium after the subsidy is withdrawn, the sustainability claim fails.","supporting_citations":[],"review_version":1}