{"id":"3da2ffc6-6db7-49d7-8849-8c326b84071b","arxiv_id":"2504.14732","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"K-UCBVI learns from K-ary episodic human feedback via maximum-likelihood reward estimation plus optimism, with a proven O(sqrt(N) log N) regret bound.","lead":"This paper proposes an RL algorithm that learns a reward function from multi-level scores (for example, 0 to 5) given at the end of each episode, instead of binary likes or pairwise comparisons. The authors prove a sublinear regret bound and test the method in grid-world simulations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Softmax shift invariance makes Sigma_Dn singular for every n, so the lambda>0 assumption in Lemma 1-Theorem 3 is impossible and the regret bound is vacuous.","rationale":"Good-faith reading: the paper proposes a K-ary categorical extension of Chatterji et al.'s binary episodic-feedback algorithm, with a UCBVI-style optimism analysis and a claimed O(sqrt(N) log N) regret bound. For that claim to hold, the MLE concentration result needs the empirical Hessian to be uniformly positive definite along all directions in the ambient R^{Kd} parameter space. That is exactly lambda_min(Sigma_Dn) >= lambda. The flaw is that the softmax parameterization has a continuous symmetry: adding the same vector u to every block w_i leaves all probabilities and the loss unchanged. Every pair difference (phi_j-phi_l) is orthogonal to the common-shift vector v=(u;...;u), so the Hessian covariance matrix Sigma_Dn annihilates v for every n. The 'well-conditioned and invertible' assumption stated after Lemma 1 cannot be satisfied, and Theorem 3's bound is undefined due to division by zero. This is a stronger failure than the reader's 'unverified covariance lower bound': it is not a missing exploration argument, because even complete exploration of all trajectories leaves the null direction intact. It also subsumes the concern about the data-dependent lambda: the minimum eigenvalue is zero a priori, so no uniform lower bound exists. The proof of strong convexity in Appendix A.1 is therefore only a seminorm bound, and the step converting to ||bw_n - w*||_2 via lambda_min is invalid. A repair is available in principle: reparameterize in terms of K-1 differences, for example by fixing w_0=0, and add explicit exploration forcing the reduced covariance to be nonsingular; the present manuscript does neither. Because the central regret guarantee is vacuous as written, the REJECT verdict is appropriate and no adjustment is needed. Agreement with reader is partial: both identify the covariance lower bound as the crux, but the reader treats it as unverified while it is actually impossible under the stated parameterization.","tokens_in":18760,"tokens_out":10281,"duration_ms":94360,"concrete_test":"Take K=2, d=1 and a single trajectory tau with phi(tau)=1, so phi_0=(1,0)^T and phi_1=(0,1)^T. Direct computation gives Sigma_D1 = (1/2) [[1,-1],[-1,1]], whose smallest eigenvalue is 0. More generally, for any n and any data set, evaluate v^T Sigma_Dn v with v=(1,...,1) in R^{Kd}; the quadratic form is 0 by the shift-invariance identity above, proving lambda_min=0. If Lemma 1 were correct, this zero eigenvalue would contradict the required lambda>0, so the check settles the singularity concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorem's guarantee rests on lambda = min_n lambda_min(Sigma_Dn) > 0 (Lemma 1, Lemma 2, Theorem 3). This assumption is not merely unverified; it is structurally false for the block-encoded features in Section 4.1. The softmax probabilities depend only on differences w_i - w_j of the K weight blocks. For any u != 0 in R^d, set v = (u;u;...;u) in R^{Kd}. For every trajectory tau and all j,l, (phi_j(tau)-phi_l(tau))^T v = u^T phi(tau) - u^T phi(tau) = 0. Hence v^T Sigma_Dn v = 0 for every n, so lambda_min(Sigma_Dn) = 0 identically, regardless of exploration or trajectory coverage. Lemma 1's bound divides by lambda_min, Lemma 2 inherits this, and Theorem 3's O(sqrt(N) log N) regret statement is vacuous. The parenthetical suggestion in Section 4.1 to use a regularized MLE when Sigma_Dn is non-invertible does not repair Theorem 3, because the theorem and all lemmas are stated and proved for the unregularized estimator and no regularization term appears in the analysis. This is an internal inconsistency, not a disagreement with prior consensus.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes K-UCBVI, an episodic reinforcement learning algorithm for settings in which, at the end of each episode, a human provides a K-level categorical score generated by a softmax over an unknown linear weight vector applied to trajectory features. Assuming known transition probabilities, the algorithm maintains a maximum-likelihood estimate of the weight vector, builds an optimistic reward estimate with a confidence bonus, and selects the policy that maximizes the optimistic value. The main theoretical claim is a high-probability cumulative regret bound of O(sqrt(N) log N) with respect to the number of episodes N (Theorem 3). The authors also present a REINFORCE-based practical approximation and grid-world experiments, including an analysis of robustness to noisy feedback.","tokens_in":19000,"tokens_out":8657,"duration_ms":81399,"significance":"If Theorem 3 were valid, the paper would extend the once-per-episode, binary-feedback analysis of Chatterji et al. (2021) to multi-level categorical feedback, with a sublinear regret guarantee and support for non-Markovian rewards. The writing is clear, the assumptions are explicitly stated, the proof appendix is detailed, and the experiments include a reasonable noise-robustness study. However, the central theoretical result is not supported: the assumed positive-definiteness of the matrix Sigma_Dn fails identically for the proposed feature encoding, and the concentration argument in Lemma 1 is applied to adaptively sampled data. The empirical evaluation cannot compensate for the collapse of the main claim.","major_comments":[{"comment":"For the block-encoded features phi_i(tau), the matrix Sigma_Dn is singular by construction. The softmax probabilities are invariant under adding any constant vector u to all weight blocks: for any u in R^d, set v=(u;...;u) in R^{Kd}. For every trajectory tau and every pair j,l, (phi_j(tau)-phi_l(tau))^T v = 0, so v^T Sigma_Dn v = 0 for every n and every realization. Hence lambda_min(Sigma_Dn) = 0 identically, and Lemma 1's bound, which divides by lambda_min(Sigma_Dn), is not a finite statement. The parenthetical suggestion of using a regularized MLE when Sigma_Dn is non-invertible does not repair the theorem, because Lemma 1, Lemma 2, and Theorem 3 are stated and proved for the unregularized estimator, and no regularization term appears in the regret bound.","section":"Section 4.1; Lemma 1; Lemma 2; Theorem 3"},{"comment":"Hoeffding's inequality is applied to the difference between the empirical loss and the true loss for a sum of terms generated under adaptively chosen policies pi^(i) that depend on previous feedback. The variables S_i are not independent, nor identically distributed, under this adaptive sampling process, so the claimed concentration statement with probability at least 1-delta is not justified as written. A martingale or self-normalized concentration argument would be needed even after the identifiability issue is repaired.","section":"Appendix A.1, Eq. (7)"},{"comment":"The assumption that Sigma_Dn is well-conditioned and invertible is not a mild regularity condition in this algorithm: Algorithm 1 contains no exploration mechanism that would ensure lambda_min(Sigma_Dn) >= lambda > 0 uniformly over episodes. If trajectories from the current policy do not excite every feature direction, the confidence bound in Lemma 1 and the regret bound in Theorem 3 become vacuous. This is an unproved coverage condition, and the theorem's guarantee depends on it in an essential way through the factor 1/lambda.","section":"Section 4.1, paragraph after Lemma 1"}],"minor_comments":[{"comment":"The policy optimization in Algorithm 1 is written with R(bw_n, tau), while the optimistic reward is defined with an overbar in Eq. (4); please make the notation consistent so that it is clear the algorithm optimizes the optimistic reward.","section":"Algorithm 1, Eq. (5)"},{"comment":"In the mean-value theorem expansion, the equation for f_i^tau(w*) is missing the term f_i^tau(bw_n) on the right-hand side; this appears to be a typographical omission.","section":"Appendix A.1, proof of Lemma 1"},{"comment":"The displayed definition of eta as 'exp(-4B) 2' is ambiguous; it should read eta = exp(-4B)/2 so that the strong-convexity constant is clear.","section":"Appendix A.1, definition of eta"},{"comment":"The experimental confidence width uses C = 10 in C/sqrt(n), whereas the theoretical constant in Theorem 3 is C = log(K exp(2B)). Please clarify that the experimental bonus is a heuristic and state explicitly how it relates to the theoretical confidence interval.","section":"Section 5.2"},{"comment":"The placement of the 'solve for bw' step inside the inner while loop is inconsistent with Algorithm 1, where the MLE is updated once per episode; please correct the pseudocode.","section":"Algorithm 2"}],"recommendation":"reject","confidential_remarks":"The main issue is not an empirical shortcoming but a structural property of the model: the positive-definiteness assumption on Sigma_Dn is impossible for the proposed block features, and the stated lemmas and theorem divide by a quantity that is identically zero. A corrected version would require a genuinely new analysis, for example with a regularized or gauge-fixed estimator and an explicit exploration or coverage condition. I would encourage the authors to rework the theory and resubmit as a new manuscript."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the stress-test note is correct. The softmax model is shift-invariant: probabilities only depend on differences w_i - w_j. With the block features in Section 4.1, the vector v = (u;...;u) is always in the null space of Sigma_Dn, so lambda_min = 0 identically. Lemma 1 divides by lambda_min, Lemma 2 inherits, and Theorem 3 is a bound with 1/0. The parenthetical about regularized MLE doesn't help because the theorem, lemmas, and proofs are all for the unregularized estimator. This is not a missing assumption; it's a structural contradiction with their own construction.\n\nThe paper does have a real contribution: the K-ary categorical feedback model is a natural generalization of Chatterji et al.'s binary logistic feedback, and the optimism-based algorithm is a sensible template. The experiments, though lacking baselines and code, do show learning in a gridworld and a robustness check. That part is fine as a proof-of-concept.\n\nThe other soft spot is the concentration argument. Lemma 1 applies Hoeffding to a sequence of loss terms sampled under policies that change with n. The samples are not i.i.d. and the 'true loss' is not a fixed function; a martingale argument would be needed. This is a serious gap, but it is the kind of thing that could be repaired.\n\nWho is this paper for? People working on theory of preference-based RL. The central theorem is vacuous as written, so I would not cite it. But the problem is worth studying, and the flaw is fixable: pin one weight (e.g., w_0 = 0) or add a sum-to-zero constraint, rederive the strong-convexity constant, and redo the concentration with martingales. If the authors do that, the result could be a solid subfield contribution.\n\nRecommendation: send it to peer review only if you believe the authors can be pushed to repair it. As is, I would not accept. It deserves a serious referee because the topic is timely and the error is non-obvious, but the current version's main claim doesn't hold.","headline":"The K-ary categorical feedback idea is reasonable, but the lambda_min assumption is impossible under the paper's own feature encoding, so the regret bound is vacuous.","tokens_in":19543,"tokens_out":3937,"would_cite":false,"duration_ms":34887,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Multilevel episode scores are enough to learn a reward model and a near-optimal policy, with cumulative regret $O(\\sqrt{N}\\log N)$.","keywords":["multi-level human feedback","episodic feedback","categorical softmax reward","reinforcement learning","optimism in the face of uncertainty","regret bound","maximum likelihood estimation","non-Markovian rewards"],"falsifier":"Run K-UCBVI in an episodic MDP with a low-dimensional trajectory feature map and check, along the algorithm's own trajectory, whether $\\lambda_{\\min}(\\Sigma_{D_n})$ ever reaches zero. If the agent repeatedly visits trajectories whose features are linearly dependent, the stated bound's $1/\\lambda$ factor is undefined; seeing whether empirical regret remains sublinear in that regime would settle whether the conditioning premise is essential.","tokens_in":18545,"feed_emoji":"🎯","tokens_out":7575,"duration_ms":66106,"temperature":0.7,"pith_summary":"This paper tries to show that a reinforcement-learning agent can learn both a reward function and a near-optimal policy when the only feedback is a coarse multilevel score, $0$ through $K-1$, given once at the end of every episode. It models the score as a softmax draw over $K$ categories driven by an unknown linear weight vector applied to a known trajectory feature map, so the expected score is the reward. The proposed algorithm, K-UCBVI, alternates maximum-likelihood estimation of the weight vector with optimistic policy selection, and the paper proves a high-probability cumulative regret bound that grows as $O(\\sqrt{N}\\log N)$ in the number of episodes $N$. If this is right, it extends the once-per-episode binary-feedback theory to richer categorical scores and offers a way to train agents from easy-to-give human ratings rather than preference pairs or dense reward engineering. The paper also reports grid-world simulations in which the algorithm learns a task from scores with $4$ or $6$ levels.","feed_headline":"K-level episode scores learn a policy with sublinear regret","feed_subtitle":"A softmax model of 0-to-K-1 ratings plus an optimistic MLE delivers a sublinear regret bound, so humans can grade whole episodes instead…","key_machinery":"The load-bearing object is the concatenated weight vector $w^\\star = [w_0^{*\\top}, \\ldots, w_{K-1}^{*\\top}]^\\top \\in \\mathbb{R}^{Kd}$, together with the block feature embedding $\\phi_i(\\tau)$ that places the trajectory feature $\\phi(\\tau)$ in the $i$-th block. The softmax score model turns the expected score $R(\\tau)$ into a generalized linear function of $w^\\star$, so learning the reward becomes learning the weight vector. The machinery carrying the proof is maximum-likelihood estimation of $w^\\star$, a strong-convexity and concentration argument that controls $\\|\\hat{w}_n - w^\\star\\|_2$ through the data-dependent matrix $\\Sigma_{D_n}$, and an optimism bonus added to the estimated reward, capped at $K-1$, so the optimistic value dominates the true value with high probability. The regret analysis then uses a martingale difference bound to convert the per-episode concentration into a cumulative regret bound. In the practical implementation, the exact optimistic policy solve is replaced by gradient ascent over softmax policies using the REINFORCE estimator.","core_discovery":"On its own terms, the paper's discovery is that $K$-ary episodic feedback is enough to identify both the reward model and a near-optimal policy. The feedback is assumed to follow a categorical softmax model, $P(y_\\tau=i) = \\exp(w_i^{*\\top}\\varphi(\\tau)) / \\sum_j \\exp(w_j^{*\\top}\\varphi(\\tau))$, with bounded trajectory features and bounded weight vectors. K-UCBVI forms a maximum-likelihood estimate of the concatenated weight vector from all past trajectory-score pairs, builds an optimistic reward by adding the estimate's confidence width, and plays the policy that maximizes the optimistic value. Theorem 3 states that, when the transition probabilities of the MDP are known, with probability at least $1-\\delta$ the cumulative regret is at most $16K\\exp(4B)/(\\eta\\lambda) \\sqrt{N C^2/2 \\log(12N/\\delta)} + 4K\\sqrt{N\\log(18N\\log N/\\delta)}$, with $\\eta=\\exp(-4B)/2$ and $C=\\log(K\\exp(2B))$; hence the regret is $O(\\sqrt{N}\\log N)$ in episodes. The paper further gives a practical version that restricts policies to softmax Markovian policies and optimizes them with a REINFORCE-style gradient step.","pith_inferences":["An extension the paper leaves implicit: because the regret constant depends on $K$ only logarithmically through $C=\\log(K\\exp(2B))$, increasing the number of feedback levels from, say, 3 to 10 should barely change the required number of episodes; this is a direct, testable prediction of the bound.","Another testable extension: the unverified conditioning assumption suggests adding an explicit exploration mechanism or regularized MLE to guarantee $\\lambda_{\\min}(\\Sigma_{D_n}) \\ge \\lambda$ with high probability, which would turn the regret theorem into a fully self-contained guarantee.","The same softmax-score formalism could be reused for non-Markovian reward learning in partially observable settings, replacing $\\phi(\\tau)$ with a bounded history embedding; the concentration argument would carry over as long as the embedding stays bounded."],"forward_implications":["A practitioner who can only grade whole episodes with a small integer score, rather than compare pairs of trajectories or design per-step rewards, has a provable method that keeps total suboptimality sublinear in the number of episodes.","Because the reward is a function of the whole trajectory, the optimal policy can be non-Markovian in general; the paper's guarantee covers this case, while the practical Markovian restriction via REINFORCE is presented as an approximation.","The regret order $O(\\sqrt{N}\\log N)$ matches the binary once-per-episode baseline, so the extra information in $K$-level scores does not cost asymptotic sample efficiency.","The optimism bonus shrinks like $1/\\sqrt{n}$, which is consistent with the empirical convergence reported in the $K=4$ and $K=6$ grid-world simulations."],"supporting_citations":[{"why":"Supplies the once-per-episode feedback problem, the optimistic MLE framework, and the martingale difference lemma that the regret proof inherits.","marker":"Chatterji et al. (2021)"},{"why":"Provides the UCBVI algorithm whose optimistic value-iteration structure K-UCBVI adapts.","marker":"Azar et al. (2017)"},{"why":"Grounds the optimistic logistic bandit analysis and the exponential-in-$B$ confidence width noted in the paper.","marker":"Faury et al. (2020)"},{"why":"Basis of the REINFORCE-style policy-gradient step used in the practical implementation.","marker":"Agarwal et al. (2019)"},{"why":"The pairwise preference model that the categorical softmax feedback model generalizes.","marker":"Bradley and Terry (1952)"},{"why":"Cited for the optimism-in-the-face-of-uncertainty principle underlying the confidence bonus.","marker":"Lattimore and Szepesvári (2020)"}],"fun_headline_variants":["K-level scores: sublinear regret without pairwise comparisons","Episode grades unlock near-optimal RL","Coarse episodic feedback still yields provable RL","Softmax model of ratings enables optimistic RL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the data-dependent matrix built from adaptively collected trajectories always has smallest eigenvalue bounded away from zero; the algorithm has no built-in exploration that guarantees this, so if the visited trajectories lie in a low-dimensional feature subspace the regret bound is vacuous.","fun_headline_variants_meta":{"raw":{"variants":["K-level scores: sublinear regret without pairwise comparisons","Episode grades unlock near-optimal RL","Coarse episodic feedback still yields provable RL","Softmax model of ratings enables optimistic RL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000217,"raw_usage":{"total_tokens":1461,"prompt_tokens":996,"completion_tokens":465,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":408}},"tokens_in":612,"tokens_out":465,"duration_ms":5176,"temperature":1.0,"reasoning_tokens":408,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:42:05.301755+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run K-UCBVI in an episodic MDP with a low-dimensional trajectory feature map and check, along the algorithm's own trajectory, whether $\\lambda_{\\min}(\\Sigma_{D_n})$ ever reaches zero. If the agent repeatedly visits trajectories whose features are linearly dependent, the stated bound's $1/\\lambda$ factor is undefined; seeing whether empirical regret remains sublinear in that regime would settle whether the conditioning premise is essential.","supporting_citations":[],"review_version":1}