{"id":"c11fd0d0-1d82-4110-9016-9c4a06bf5571","arxiv_id":"2502.07593","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The greedy strategy of choosing the highest observed average rating has minimax-optimal worst-case regret 1/8 in a two-product, two-rating, one-observation game, and its regret tends to zero with more observations, but the claim that Thompson Sampling retains positive regret is flawed.","lead":"This paper studies whether picking the product with the highest average rating is a good idea when you only have a few noisy reviews and know nothing about the true quality. It finds that in a worst-case game against an adversary this greedy choice is optimal in a simple two-product case and its regret shrinks as reviews grow, but a key claim about beating a standard Bayesian algorithm contains an error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5's claim that Thompson Sampling retains positive regret as m→∞ is false because the proof ignores posterior concentration; the advertised asymptotic superiority of greedy over TS is unsupported.","rationale":"The reader's weakest_assumption focuses on the equal-number-of-observations restriction, which is a scope limitation rather than an internal error. However, the reader's rationale also identifies Proposition 5 as false, and that is the most load-bearing concern: it attacks a headline theoretical claim of the paper and invalidates the advertised asymptotic comparison with Thompson Sampling. The small-case minimax results (Propositions 1 and 2) appear sound, and the equal-m restriction is explicitly stated, so I would not reject the paper on those grounds. The proof of Theorem 4 has a genuine uniformity gap (the maximum over states is taken after fixing a state, and the Hoeffding bound depends on the state gap Δ), though the conclusion that worst-case regret tends to zero may still be true via a more careful argument. Proposition 5, by contrast, asserts a false conclusion: the posterior of Thompson Sampling concentrates, so its regret tends to zero just like greedy's. The proof's error is not merely a missing supremum argument; it mischaracterizes the limiting behavior of the observation matrix and the posterior. Because the abstract, results overview, and empirical evaluation all highlight the asymptotic outperformance of greedy over TS, this false claim is central to the paper's contribution. A corrected paper could remove the asymptotic TS claim and still retain the finite-sample minimax results, but as submitted the central advertised comparison is unsupported and, in fact, false. Hence the reader's REJECT verdict is appropriate, and no change to that verdict is needed. I agree with the reader's overall rejection, though my primary concern differs from their stated weakest_assumption.","tokens_in":15079,"tokens_out":7332,"duration_ms":65186,"concrete_test":"Numerically compute the exact Thompson Sampling regret for nd=2, nr=2, state p1=0.4, p2=0.6 (product 1 has higher expected value) at m=100, 1000, 10000 using the paper's formula: regret = Σ_B P[B|S'] P(X<Y) (p2-p1), where X~Beta(b,a), Y~Beta(d,c). If the computed regret tends to 0 (e.g., below 0.001 at m=10000) instead of approaching a positive constant, Proposition 5 is refuted. For an analytical check, bound P(X<Y) for typical B by exp(-c m) using standard Beta concentration inequalities, and verify that atypical B contribute negligibly, yielding total regret → 0.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advertised claim in the Abstract, Results Overview item 5, and Section 4.5 is that greedy outperforms Thompson Sampling even as the number of observations goes to infinity. Proposition 5 attempts to prove this by arguing that for observation matrices B' with b>d (which occur with probability approaching 1), the Thompson Sampling mistake probability P(X<Y) is positive for 'some a,b,c,d>0', hence TS incurs positive limiting regret. This is a non sequitur: as m→∞, the observation counts a,b,c,d in the probability-dominant matrices grow linearly with m (e.g., b≈m(1-p1), d≈m(1-p2) when product 1 is better). The Beta posteriors then concentrate around their means, and P(X<Y) tends to 0 exponentially for the very matrices that dominate the sum. The proof treats a,b,c,d as fixed constants as m→∞, but they are m-dependent random quantities; the limiting regret is not a single term P(X<Y)(p2-p1) evaluated at an arbitrary matrix, but a sum over the full distribution of B. A correct analysis shows the Thompson Sampling regret also converges to 0 as m→∞. Therefore the claimed asymptotic separation between greedy and TS is false, and the paper's headline comparison—central to both the theory and the empirical narrative—rests on an invalid argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper analyzes a one-shot decision problem in which Nature chooses an arbitrary per-product rating distribution, the decision-maker observes exactly m ratings for each of nd products, and a strategy maps the observation matrix to a product. The authors define worst-case expected regret, prove that for nd = nr = 2 and m = 1 the greedy strategy achieves worst-case regret 1/8 and that no strategy can do better (Propositions 1 and 2), numerically show that this value decreases for m up to 20, state an asymptotic zero-regret theorem (Theorem 4), and claim that greedy outperforms Thompson Sampling even as m goes to infinity (Proposition 5). They also simulate the strategy on Google restaurant reviews data and report that greedy has lower regret than uniform and Thompson Sampling in finite samples.","tokens_in":15344,"tokens_out":8788,"duration_ms":86792,"significance":"The exact minimax constant 1/8 is a clean and correct result, and the equal-observation model is internally coherent. Propositions 1 and 2 are self-contained and their computations check out. The numerical decay and the empirical setup are plausible. However, the advertised asymptotic separation from Thompson Sampling is not established: Proposition 5's proof is invalid in the way identified by the stress-test note, and once that claim is removed the central theoretical contribution is a minimax analysis of greedy under a restrictive equal-sample-size assumption. With a repaired uniform proof for Theorem 4, the worst-case convergence result would still be a useful contribution, but the paper's current abstract substantially overstates the results.","major_comments":[{"comment":"The asymptotic argument is invalid. The proof fixes a generic observation matrix B' with b > d and argues that P(X < Y) > 0 for some a,b,c,d > 0, then takes m to infinity and concludes that Thompson Sampling incurs positive regret. But a,b,c,d are m-dependent random counts: under the state S' with p1 < p2, the matrices that dominate the probability mass have b ≈ m(1-p1), d ≈ m(1-p2), a ≈ m p1, c ≈ m p2, and for these matrices the Beta posteriors concentrate, so P(X < Y) tends to 0 exponentially. The limiting regret is not a single term P(X < Y)(p2 - p1) evaluated at an arbitrary matrix; it is a sum over the full distribution of the observation matrix. A correct analysis shows that the Thompson Sampling regret also converges to 0 as m grows. Therefore the claimed asymptotic separation in the Abstract, in Results Overview item 5, and in the last paragraph of Section 4.5 is unsupported and, as stated, false.","section":"§4.5, Proposition 5"},{"comment":"The proof is not uniform over states. The final bound nd exp(-m(VS*(d1) - VS*(d2))^2 / (2(nr-1)^2)) depends on the state-specific gap VS*(d1) - VS*(d2), and the sentence 'WLOG we can pick a single state S*' does not justify exchanging the supremum over states with a pointwise argument. The worst-case state can change with m, and gaps arbitrarily close to zero are allowed in the state space. To prove γ(σg) → 0 one must either optimize the product of the gap and the misclassification probability or give a uniform concentration argument; the proof as written only establishes pointwise convergence for each fixed state. The claim may be salvageable, but the current proof is not sufficient for the stated worst-case result.","section":"§4.4, Theorem 4"},{"comment":"The empirical comparison to Thompson Sampling is currently the only remaining support for the claim that greedy outperforms Thompson Sampling, because the theoretical comparison in Proposition 5 is invalid. The simulation uses a smoothing constant for zero-count Beta parameters that is never specified (footnote 3), and it reports point estimates without confidence intervals or other variability measures, so the finite-sample superiority of greedy over Thompson Sampling is not yet established as a robust finding. The full-data average is also used both to define the ground-truth state and to evaluate regret, which makes the simulation a test of agreement with an empirical proxy rather than with the true state; the paper should state this limitation explicitly and, ideally, add a sensitivity analysis for the smoothing value.","section":"§5, Simulation Result 6"}],"minor_comments":[{"comment":"The displayed formula for π(σg, S') appears to contain a typo; based on the regret formula it should be 2 - p1/2 - p2/2 + (p1 - p2)^2/2, not 2 - p1 + p2/2 + (p1 - p2)^2/2. The regret calculation itself is consistent.","section":"§4.1, Proposition 1 proof"},{"comment":"The statement 'the greedy strategy has a regret of 0 with probability 1 - δ' conflates the random event of selecting the best product with the expected regret; the paper should either define a random regret or rephrase the claim as 'picks the best product with probability at least 1 - δ'.","section":"Theorem 4 statement"},{"comment":"The claim that greedy is 'optimal' should be qualified as holding for two products, two ratings, and one observation per product; as written, the Abstract and Results Overview overstate the scope of Proposition 2.","section":"§1.1 and Abstract"},{"comment":"The footnote says Proposition 5 can be generalized to any number of ratings and products by replacing Beta with Dirichlet and taking a union bound, but no proof is given; either provide the proof or remove the assertion.","section":"§4.5, footnote 4"},{"comment":"The figure would benefit from confidence bands or standard errors, since the tables show small differences between greedy and Thompson Sampling in several cells; the tables themselves are helpful and should remain.","section":"Figure 2 and Appendix A"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the manuscript's most eye-catching claim, the asymptotic separation from Thompson Sampling, is not merely unproved but false under the standard concentration of Beta posteriors. I would not accept the paper without removing that claim and rewriting the Abstract, Results Overview, and Section 4.5 accordingly. The remaining minimax results are correct but substantially narrower than the current title and abstract suggest."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe part of this paper that is actually new is worth your time: for the two-product, two-rating, one-observation case, they pin the worst-case regret of the greedy rule at exactly 1/8, and they prove no strategy can do better. That is a clean, correct application of Wald/Savage minimax regret to a discrete rating setting. The numerical curve for m up to 20 is also a legitimate extension, and the Google reviews experiment, while simple, does show greedy's regret dropping as the observation count grows.\n\nThe problem is the headline. Proposition 5 claims Thompson Sampling has positive regret even as m→∞. That is false. The proof fixes an arbitrary observation matrix B' with b>d and notes P(X<Y)>0 for some positive counts, then concludes the limiting regret is positive. But the a,b,c,d are not fixed as m grows; they scale with m. The matrices that dominate the probability mass have b≈m(1−p1), d≈m(1−p2), and the Beta posteriors concentrate, so P(X<Y) tends to 0 exponentially. Sum the regret over the full distribution of B and it also goes to 0. The claimed asymptotic separation between greedy and Thompson Sampling is unsupported.\n\nThere is a second soft spot: Theorem 4 says γ(σg)→0, but the proof fixes a state and derives a bound depending on the value gap. To conclude the worst-case regret vanishes you need a supremum over states, and states with tiny gaps require huge m. The conclusion may be true—the numeric evidence suggests it—but the argument as written does not establish it.\n\nThe equal-sample-size assumption (every product observed exactly m times) is a real limitation, and the paper's Section 6 shows greedy can fail badly with unbalanced counts. The authors acknowledge this and leave it for future work, so I treat it as a constraint, not a hidden flaw. The empirical evaluation uses the same data to define the ground truth and to evaluate regret, which is circular as a validation, but it is a reasonable sanity check, not a claimed proof.\n\nBottom line: the small-case minimax results are solid and deserve publication in some form, but the paper as it stands overclaims. If I were the editor, I would send it to review, but I would expect the authors to fix or drop Proposition 5 and to make Theorem 4's convergence argument uniform before acceptance.","headline":"The minimax results for the greedy rule are real, but the advertised asymptotic separation from Thompson Sampling rests on a faulty argument.","tokens_in":15870,"tokens_out":3804,"would_cite":true,"duration_ms":35483,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A05","62C20","91B06"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that when every product is observed the same number of times, the greedy strategy of picking the highest average rating is minimax-optimal for worst-case regret, with regret shrinking to zero as observations grow.","keywords":["worst-case regret","greedy strategy","complete uncertainty","Knightian uncertainty","minimax regret","Thompson Sampling","multi-armed bandit","decision theory"],"falsifier":"For a fixed two-product state with rating probabilities $(p_1,p_2)$, compute the expected Thompson Sampling regret exactly for increasing $m$ by summing the closed-form Beta-Binomial expression over all observation matrices; if the expectation decays to $0$ rather than approaching a positive constant, Proposition 5 fails. Separately, run greedy on data where one product has many more reviews than another and record how often it selects the product with the lower true average; a high mis-selection rate would confirm the equal-sample-size limit of the theorem.","tokens_in":14863,"feed_emoji":"⭐","tokens_out":12039,"duration_ms":86108,"temperature":0.7,"pith_summary":"The paper studies a one-shot decision problem under complete uncertainty: a decision maker sees $m$ star-rating observations for each of several products, with no knowledge of the underlying rating distributions, and must pick one product. It claims that the greedy strategy—choose the product with the highest observed average rating, breaking ties uniformly—is optimal with respect to worst-case regret: no other strategy can guarantee a lower maximum regret, and as $m$ grows the greedy rule's worst-case regret converges to zero. For the simplest case of two products, two ratings, and one observation per product, the paper proves the worst-case regret is exactly $\\frac{1}{8}$ and that this is the best any strategy can do. It also argues that Thompson Sampling, a standard Bayesian alternative, incurs positive regret even as $m$ tends to infinity, and it reports simulations on Google restaurant reviews in which greedy outperforms both the uniform rule and Thompson Sampling. The significance, if the claims hold, is that a decision maker facing unknown distributions can do no better than the simple rule of picking the observed best.","feed_headline":"Greedy rating rule has the lowest possible worst-case regret","feed_subtitle":"A minimax proof says the highest-average rule has the lowest worst-case regret; regret falls to zero with more reviews.","key_machinery":"The central object is the observation matrix $B$, whose columns are constrained to sum to $m$ (equal observations per product), and the strategy $\\sigma_g$ that maps $B$ to the product(s) maximizing the observed average $V_B(d)$. The argument runs through the worst-case regret functional $\\gamma(\\sigma)=\\max_S[\\max_d V_S(d)-\\pi(\\sigma,S)]$, the two-state adversarial construction in Proposition 2 (states $S_1$ and $S_2$ that force any tie-breaking probability $p$ to incur regret at least $\\frac{1}{8}$), and a Hoeffding concentration bound on the gap between the top two products' empirical sums to prove the limit result. For Thompson Sampling, the machinery is the Beta-Binomial distribution of sampled posterior ratings; the paper integrates $P(X<Y)$ to derive its expected regret.","core_discovery":"The central discovery is that, in a zero-sum game against Nature where Nature chooses any column-stochastic rating matrix and the decision maker only sees an observation matrix with exactly $m$ independent ratings per product, the greedy strategy $\\sigma_g$ is minimax-optimal for worst-case regret $\\gamma(\\sigma) = \\max_S (\\max_d V_S(d) - \\pi(\\sigma,S))$. For two products, two ratings, and $m=1$, the paper proves $\\gamma(\\sigma_g)=\\frac{1}{8}$ (Proposition 1) and proves a matching lower bound for all strategies (Proposition 2), so no decision rule can do better in the worst case. It then shows numerically that $\\gamma$ decreases with $m$ up to 20 and proves via a Hoeffding bound (Theorem 4) that $\\gamma \\to 0$ as $m \\to \\infty$, with an explicit sample size sufficient for zero regret with probability $1-\\delta$. Finally, Proposition 5 claims that for two products and two ratings, Thompson Sampling's regret does not vanish as $m \\to \\infty$, whereas greedy's does.","pith_inferences":["If the equal-sample-size condition is dropped, the greedy rule can be arbitrarily bad (as the paper's Section 6 example shows), so the practical guidance 'always pick the highest average' should be read as conditional on comparable sample sizes; a confidence-aware variant such as a lower-confidence bound would be the natural extension.","The minimax optimality result is proven only for the $m=1$, two-product, two-rating case; extending the lower-bound technique to larger $m$ and more products would be needed before claiming the greedy rule is minimax-optimal generally.","The paper's asymptotic comparison with Thompson Sampling, if correct, would reverse the usual bandit wisdom that greedy starves exploration; a fruitful test is whether the conclusion survives with unequal observation counts, where Thompson Sampling's built-in uncertainty adjustment may matter.","Because the theorem's zero-regret guarantee is stated with probability $1-\\delta$, it is a high-probability statement, not an almost-sure guarantee; a decision maker who needs certainty would still need the explicit sample size formula rather than relying on the limit."],"forward_implications":["For the binary two-product case with one observation per product, the greedy rule guarantees regret at most $\\frac{1}{8}$, and no strategy can guarantee less; a decision maker who only sees one rating per option is assured of capturing at least $\\frac{7}{8}$ of the value gap.","As the number of observations per product grows, greedy's worst-case regret tends to $0$; Theorem 4 gives an explicit $m$ needed to achieve zero regret with probability $1-\\delta$.","The greedy rule's worst-case regret decreases over the range $m=1,\\dots,20$ in the binary case, and the empirical study on 1.5 million Google reviews confirms decreasing regret with more reviews across up to 10 products.","Thompson Sampling, despite being a standard Bayesian bandit method, is claimed to incur positive regret even in the infinite-observation limit, making it worse than greedy in this worst-case one-shot sense.","For settings with equal observation counts, a quality-control agent can use $m$ and the rating gap to bound the maximum regret of picking the batch with the highest observed average quality."],"supporting_citations":[{"why":"Defines the minimax-regret criterion that the paper's worst-case measure is based on.","marker":"[17]"},{"why":"Supplies the maximin worst-case decision framework for the game against Nature.","marker":"[19]"},{"why":"Introduces the randomized greedy algorithm with uniform tie-breaking that the paper analyzes.","marker":"[6]"},{"why":"Specifies the Thompson Sampling algorithm used as the Bayesian baseline.","marker":"[16]"},{"why":"Provides the Google restaurant reviews dataset for empirical validation.","marker":"[21]"},{"why":"Motivates measuring worst-case expected regret for the greedy strategy.","marker":"[11]"},{"why":"Supports the equivalence of expected and pseudo-regret used in the one-shot setting.","marker":"[1]"}],"fun_headline_variants":["Greedy rule is minimax-optimal for worst-case regret","Greedy strategy minimizes worst-case regret under Knightian uncertainty","Worst-case regret zero as reviews grow for greedy rule","Greedy beats Thompson Sampling in worst-case regret","Greedy minimax optimal: regret vanishes with more data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole theory requires that every product is observed exactly the same number of times $m$; if observation counts differ, the paper's own example shows the greedy rule can pick a product whose true value is far below another, and none of the minimax or convergence guarantees apply.","fun_headline_variants_meta":{"raw":{"variants":["Greedy rule is minimax-optimal for worst-case regret","Greedy strategy minimizes worst-case regret under Knightian uncertainty","Worst-case regret zero as reviews grow for greedy rule","Greedy beats Thompson Sampling in worst-case regret","Greedy minimax optimal: regret vanishes with more data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2846,"prompt_tokens":938,"completion_tokens":1908,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":1824}},"tokens_in":554,"tokens_out":1908,"duration_ms":12607,"temperature":1.0,"reasoning_tokens":1824,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T12:13:30.988799+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed two-product state with rating probabilities $(p_1,p_2)$, compute the expected Thompson Sampling regret exactly for increasing $m$ by summing the closed-form Beta-Binomial expression over all observation matrices; if the expectation decays to $0$ rather than approaching a positive constant, Proposition 5 fails. Separately, run greedy on data where one product has many more reviews than another and record how often it selects the product with the lower true average; a high mis-selection rate would confirm the equal-sample-size limit of the theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the minimax-regret criterion that the paper's worst-case measure is based on."},{"cited_title":"Learning, Regret Minimization, and Equilibria, page 79–102","cited_arxiv_id":null,"evidence_quote":"Introduces the randomized greedy algorithm with uniform tie-breaking that the paper analyzes."},{"cited_title":"Personalized showcases: Generating multi-modal explanations for recom- mendations, 2023","cited_arxiv_id":null,"evidence_quote":"Provides the Google restaurant reviews dataset for empirical validation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates measuring worst-case expected regret for the greedy strategy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the equivalence of expected and pseudo-regret used in the one-shot setting."}],"review_version":1}