acceptodds
Under review as a conference paper at ICLR 2027

Confidence-Guided Policy Optimization: Thompson Sampling and UCB Trees for Group-Relative Code Refinement

Abstract

Group-relative policy optimization methods, such as GRPO, learn from the relative reward of trajectories sampled for the same prompt. When every trajectory in a group receives the same reward, the centered advantages vanish and the group contributes no policy-gradient signal, even though the environment was queried and feedback was obtained. We introduce Confidence-Guided Policy Refinement (CGPR), a training-time framework that uses this feedback to convert such uninformative groups into informative ones, rather than discarding them and resampling independently. CGPR builds a bounded refinement tree over the trajectories of an uninformative group and evaluates two budget-allocation strategies for expanding that tree: a UCB-style rule (CVPR) and a Thompson-Sampling rule (CGPR-TS) based on a Beta posterior over per-node success probability. A candidate replaces a non-anchor trajectory only when it increases the reward dispersion of the group, and a highest-reward anchor trajectory is never replaced. Refinement occurs only during training and adds no inference-time computation. All experiments use the same Qwen3-4B-Instruct backbone. Across HumanEval(+), MBPP(+), APPS, Codeforces, and LiveCodeBench, the two CGPR variants improve over vanilla GRPO on the more challenging APPS and Codeforces benchmarks, while their effects on HumanEval(+), MBPP(+), and LiveCodeBench depend on the metric and allocation strategy. Relative to GRPO, the largest pass@1 and pass@10 gains are both percentage points, achieved by CVPR on Codeforces. CGPR-TS obtains the strongest MBPP(+) pass@1/pass@10 and LiveCodeBench pass@1 among the fine-tuned methods, while CVPR obtains the strongest APPS and Codeforces results. DAPO obtains the strongest HumanEval(+) pass@1/pass@10 and LiveCodeBench pass@10 among the fine-tuned methods.

Primary area:
reinforcement learning
Keywords:
LLM post-training, group relative policy optimization (GRPO), Thompson sampling, upper confidence bound (UCB), code generation

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 2 reviews, above 68% of the others.
Reviewer_mHknOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Confidence-Guided Policy Refinement (CGPR), a training-time framework for recovering learning signals from low-dispersion rollout groups in GRPO-based code generation. When an initial group provides little reward contrast, the method constructs a bounded tree of feedback-conditioned code refinements and allocates the search budget using either a UCB-style rule (CVPR) or Thompson sampling (CGPR-TS). A refined candidate replaces a non-anchor trajectory only when it increases group reward variance, while one highest-reward trajectory from the initial group is preserved. The resulting fixed-size group is then used for policy optimization without changing the inference procedure. Experiments with Qwen3-4B-Instruct show improvements over GRPO on APPS and Codeforces, including a 5.0-percentage-point gain in both pass@1 and pass@10 on Codeforces. However, results on the remaining benchmarks are mixed, and several methodological and experimental issues limit the strength of the conclusions.

Critical strengths
  • The paper addresses a concrete limitation of GRPO. When all trajectories receive the same reward, group-centered advantages vanish. Reusing execution feedback from these groups is a sensible way to seek additional useful training examples, particularly when independent generation repeatedly fails.

  • The framework is practical and insightful. Refinement is confined to training, so the method does not require additional search or verifier calls at inference time. Keeping the backbone and reward fixed across the principal GRPO-based comparisons also helps control some sources of variation.

  • The improvements on harder benchmarks are promising. Both variants improve APPS and Codeforces pass@1 and pass@10 relative to GRPO. The paper also reports unfavorable results and acknowledges that the benefits are not uniform, together with the additional training cost and distributional mismatch.

Critical weaknesses
  1. Refinements are sampled conditional on the parent program and execution feedback in Eq. (4), whereas their likelihoods in the GRPO update are evaluated under the original prompt, as explicitly acknowledged in Section 6. Adaptive tree selection and variance-based acceptance further change the distribution of the training groups. Please specify the objective under the actual group-construction distribution and explain which aspects of the update are heuristic.

  2. Table 1 describes the fine-tuned methods as compute-matched, but Section 5.1 establishes matching optimizer updates rather than total training resources. Figure 2 reports additional rollout expenditure, and Section 6 reports a 37.5% wall-clock increase relative to GRPO. Equal update counts therefore do not separate the benefit of better group construction from the benefit of additional generation and verification. This distinction is particularly relevant because the proposed method explicitly spends extra interactions on selected training examples. Please clarify or correct the comparison label and include at least one downstream comparison at a matched total rollout-token or GPU-hour budget.

  3. The comparison between UCB and Thompson sampling does not establish that confidence-guided allocation outperforms simpler feedback-conditioned refinement. It is better to provide more expreiment on Uniform or greedy expansion versus UCB/Thompson sampling. and Variance-based acceptance versus reward-improving acceptance.

  4. Table 1 claims five-seed averages and 95% bootstrap confidence intervals, but only point estimates are shown. Appendix C lists seeds under inference settings without clarifying whether they correspond to independent training runs, decoding runs, or both.

Questions for authors
  1. How are newly created nodes and expansion counts initialized in Eq. (5)? If a new node has zero prior expansions, the reported ϵ=10−6\epsilon=10^{-6} makes its exploration bonus overwhelmingly larger than that of a previously expanded node. Under the 16-candidate budget, does the implementation therefore behave mainly as greedy selection among unexpanded nodes? Please provide pseudocode or a short expansion trace.

  2. What precisely counts as an unsuccessful refinement in Eqs. (6)–(7)? Does it mean failing all tests, failing to improve reward, or failing the variance-acceptance criterion? How is the Beta distribution updated after a successful refinement, and are successful parents retired? These details are necessary to interpret the stated posterior over refinement success.

  3. Which variant does the single CGPR curve in Figure 2 represent? Are the reported fractions measured before or after refinement? Does “uninformative” mean exactly equal rewards or variance below the configured threshold? Reporting both pre-refinement and post-refinement fractions for the same groups would make the diagnostic easier to interpret.

1 comment

Thank you for the detailed review. Several of the changes in the revision come directly from your questions, especially the one about UCB initialization. Note that we renamed the UCB variant from "CVPR" to CGPR-UCB, which matches CGPR-TS and avoids the clash with the conference name.

W1 (objective under the actual distribution). This is now Sec. 4.3. We write CGPR's objective as the clipped GRPO surrogate taken over the group distribution induced by our construction (initial sampling, feedback-conditioned proposals, adaptive selection, variance-gated replacement), with all trajectories scored under x. Groups that are informative from the start, the anchor, and un-replaced trajectories are on-policy. The importance ratio of replaced trajectories, the tree selection and the variance gating are heuristic and uncorrected. We relate the resulting update to STaR rationalization and make no convergence claim.

W2 (compute-matched label). Corrected to "update-matched" in the Table 1 caption and in Sec. 5.1. We have not yet run a GRPO baseline at matched total rollout budget. In the meantime, the paper reports per-informative-group token cost (Fig. 2b: CGPR 1.17x to 1.65x vs DAPO 1.4x to 2.1x of GRPO) and the 37.5% wall-clock overhead. Sec. 6 states that part of the gain over GRPO may come from the extra interaction. We plan to add the budget-matched run for the final version.

W3 (simpler baselines, acceptance rule). Added in Sec. 5.3 and Table 2 (pass@1, APPS / Codeforces): Random 23.5 / 18.2, Greedy 23.1 / 18.8, UCB 25.2 / 20.6, TS 24.5 / 20.7, against GRPO at 22.5 / 16.0. At the same refinement budget, UCB and TS beat the better of the two simple rules by 1.0 to 1.9 pp, and Greedy is not better than Random. On variance-based vs reward-improving acceptance, we did not run the comparison in this revision. Sec. 4.2 now states when a lower-reward candidate can be accepted: only in uninformative groups that share a non-zero partial reward, never in all-failed groups, since R = 0 is the minimum. Sec. 6 lists the reward-improving variant as open.

W4 (CIs and seeds). The Table 1 caption no longer claims intervals it does not show. Results are means over five seeds (42, 123, 456, 789, 999). CIs are percentile bootstrap over test problems. For GRPO and CGPR-UCB on HumanEval(+) and MBPP(+), the half-widths are at most 0.9 pp, so we now treat differences on those two benchmarks as noise (Sec. 5.1, 5.2). The full per-entry CI table will go into the final version.

Q1 (UCB initialization). Your reading is correct. New nodes start with N_v = 0, so with eps = 1e-6 any unexpanded node outscores every expanded one, and all unexpanded nodes get the same bonus. Appendix F shows that with G = 4, depth 5 and a budget of 16, an unexpanded expandable node always exists. In our configuration, CGPR-UCB therefore never expands a node twice: it is best-first expansion of unrefined attempts by reward, and C has no effect. Sec. 4.1 and Sec. 6 now say this directly. It is not quite greedy, though. Our Greedy baseline keeps re-expanding the current best node, and UCB beats it by 2.1 pp on APPS and 1.8 pp on Codeforces. Pseudocode is in Algorithm 1 (App. E), and App. F walks through the expansion order.

Q2 (TS update). An attempt from node rho is unsuccessful if the child does not improve on the parent, R(rho') <= R(rho). Each failure increments N_rho and thus beta_rho. A new node starts from the reward-based prior Beta(1 + C R_norm, 1 + C (1 - R_norm)) with N = 0. Parents are not retired and stay expandable until they reach the branching factor. Since successes never increment alpha, this is a pseudo-posterior (reward prior plus a failure penalty, similar to the arm penalty in REx) rather than an exact Bayesian posterior; Sec. 4.1 now uses that wording.

Q3 (Figure 2). "Uninformative" means V < tau_group = 1e-4, the same test that triggers refinement, so it includes exact ties and slightly more. For CGPR, the plotted fraction is measured after refinement, on the groups actually passed to the update. Both points are now stated in Sec. 5.4 and in the caption. We agree that pre-refinement fractions for the same groups would make the plot easier to read and will add them.

Reviewer_HUsPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Confidence-Guided Policy Refinement (CGPR), a training-time framework for improving GRPO-based code debugging. It constructs refinement trees from uninformative rollout groups and uses UCB or Thompson Sampling to allocate refinement budgets. Candidates are accepted based on their contribution to reward dispersion. Experiments on five coding benchmarks evaluate its effectiveness in improving code generation performance and reducing wasted rollouts.

Critical strengths
  1. The paper addresses an important limitation of GRPO by reusing feedback from uninformative rollout groups to construct more informative training experiences.

  2. The proposed framework demonstrates promising improvements on challenging coding benchmarks, particularly APPS and Codeforces, while reducing rollout-token costs per informative group compared with DAPO.

Critical weaknesses
  1. The feedback-conditioned refinement introduces an off-policy mismatch in the GRPO objective, raising concerns about the correctness of the policy gradient. The theoretical analysis does not address this issue.

  2. The empirical gains are inconsistent across benchmarks, while training time increases by 37.5%. The lack of compute-matched comparisons and sufficient ablations weakens the evidence for the proposed method.

Questions for authors
  1. What empirical evidence supports the assumption that feedback-conditioned refinement is more effective than independent resampling?

  2. How is the off-policy mismatch between feedback-conditioned sampling and the GRPO objective addressed?

  3. How much improvement comes from UCB or Thompson Sampling compared with simpler refinement strategies?

  4. Do the performance gains persist under equal computational budgets, given the additional 37.5% training time?

1 comment

Thank you for the review. Below we go through your four questions; the corresponding changes are in the revised PDF.

Q1. Evidence that feedback-conditioned refinement beats independent resampling. We have two pieces of evidence, both indirect. First, DAPO is effectively the independent-resampling baseline: it discards uninformative groups and samples new ones. Fig. 2(b) shows that DAPO needs 1.4x to 2.1x the rollout tokens of GRPO per informative group over training, while CGPR needs 1.17x to 1.65x. Refining failed attempts therefore yields informative groups more cheaply than resampling them, which is what q' > q in Proposition 3.2 would predict. Second, the new allocation ablation (Table 2) shows that refinement improves pass@1 over GRPO even when the node to refine is chosen at random (+1.0 pp on APPS, +2.2 pp on Codeforces). That comparison is not budget-matched, so we do not present it as proof. We do not estimate q and q' directly, and Sec. 3.2 now says this explicitly. We also added Remark 3.3, which states that the proposition only covers all-failed groups.

Q2. The off-policy mismatch. You are right that the original analysis did not address it. The new Sec. 4.3 writes down what CGPR actually optimizes: the clipped GRPO surrogate taken in expectation over the group distribution produced by our construction, with every trajectory (including refined ones) scored under the original prompt x. Groups that are informative from the start, the anchor, and all un-replaced trajectories are on-policy. Replaced trajectories are not: their importance ratio uses pi_old(y'|x) instead of pi_old(y'|x, y_v, f_v), and we do not correct for that, or for the tree selection and variance gating. At theta = theta_old, the update on a refined program is an advantage-weighted likelihood step taken as if the program had come from x alone. This is the same construction as rationalization in STaR, which samples with a hint and trains without it. We describe the result as a biased surrogate and no longer make any claim about the correctness of the on-policy gradient. We have not yet measured the size of the mismatch; Sec. 6 says so.

Q3. UCB/TS vs simpler allocation. We ran this ablation (Sec. 5.3, Table 2). Tree limits, refinement budget, reward, anchor, acceptance rule and number of updates are identical across rules; only the choice of node to expand changes. pass@1 on APPS / Codeforces:

  • GRPO 22.5 / 16.0
  • Random 23.5 / 18.2
  • Greedy 23.1 / 18.8
  • UCB 25.2 / 20.6
  • TS 24.5 / 20.7

At the same budget, UCB and TS are 1.0 to 1.9 pp above the better of Random and Greedy, and roughly double the gain that random allocation gives over GRPO. Greedy is no better than Random.

Q4. Equal compute. We agree that "compute-matched" was the wrong label. The methods are matched in optimizer updates, group size and batch size, not in rollout budget, and the paper now calls them update-matched. What we can say at the moment: DAPO spends more rollout tokens per informative group than CGPR and is still weaker on APPS and Codeforces; and within CGPR, where the extra budget is held fixed, the allocation rule alone accounts for 1.0 to 1.9 pp. We have not run GRPO with a matched total rollout budget (e.g., a larger group size). Some of the gain over GRPO could therefore come from the extra interaction itself. Sec. 6 states this, and we will add that baseline in the final version.

On inconsistent gains: we agree, and the revised Sec. 5.2 is more explicit about it. The improvements are on APPS and Codeforces; on HumanEval(+) and MBPP(+) the differences between fine-tuned methods are about the size of the confidence intervals, and we no longer claim gains there.

If the revision resolves the soundness concerns for you, we would appreciate it if you could reconsider your score.

Comments on the paper

1 comment

Thank you for the review. Several of your criticisms were justified, and we have tried to fix what could be fixed within the discussion period. Where something has not been done, we say so below.

Q1. Training data and overlap. All fine-tuned methods are trained on the same set of Python programming problems with unit tests, and the training reward uses only those tests. Hyperparameters were tuned on a held-out validation split, not on evaluation benchmarks. Sec. 5.1 now describes this. The explicit contamination safeguard reported in the paper is the LiveCodeBench window (Oct 2024 to Feb 2025), which we treat as temporally held out; given known contamination of older code benchmarks (Riddell et al., 2024), the HumanEval(+) and MBPP(+) numbers should be read with that in mind.

Q2. Same total rollout budget. We have not run GRPO or DAPO with a larger group size at matched total budget yet, and we will add it for the final version. The paper no longer calls the comparison compute-matched; it is update-matched. Two observations bear on the question in the meantime. DAPO spends more rollout tokens per informative group than CGPR (Fig. 2b) and is still weaker on APPS and Codeforces. And in the new ablation, the extra refinement budget is identical across allocation rules, yet UCB and TS gain 1.0 to 1.9 pp over random or greedy allocation. Sec. 6 states that part of CGPR's gain over GRPO may still come from the extra interaction.

Q3. Lower-reward accepted candidates. You are right that the variance-gain rule does not care about the direction of the change; Sec. 4.2 now says so. It cannot admit a worse trajectory in an all-failed group, because R = 0 is the minimum reward. It can do so in uninformative groups that share a non-zero partial reward (e.g., same static-analysis credit). We have not measured how often that happens, and we have not trained with a reward-improving acceptance rule. Both are listed as open in Sec. 6. On the proposition: Remark 3.3 now states that it covers only the all-failed case, and Sec. 3.2 says that we do not estimate q and q' directly.

Q4. Random expansion baseline. Added (Sec. 5.3, Table 2), with everything except the allocation rule held fixed. pass@1 on APPS / Codeforces: Random 23.5 / 18.2, Greedy 23.1 / 18.8, UCB 25.2 / 20.6, TS 24.5 / 20.7 (GRPO 22.5 / 16.0). Both allocation rules beat random expansion at the same budget. You are also right that UCB and TS are hard to tell apart: they are within 0.7 pp of each other, and we no longer argue for one over the other. Appendix F explains part of the reason: with our budget, UCB never re-expands a node, so it acts as best-first expansion of unrefined attempts. We did not ablate the anchor or the budget in this revision.

Q5. Size of the off-policy effect. Not measured yet. What the revision adds is Sec. 4.3, which writes down the surrogate objective CGPR optimizes. It says which parts are on-policy (initially informative groups, the anchor, un-replaced trajectories) and which are not corrected (the ratio of refined trajectories, the tree selection, the variance gating). It also connects the update to STaR rationalization. We make no convergence claim. Sec. 6 describes the measurement you suggest as future work.

State of the manuscript. We agree the submitted version was not in good shape, and we apologize.

  • The AI-use statement is now filled in.
  • The training set is described in Sec. 5.1.
  • Algorithm 1 (App. E) gives the exact procedure. Where Figure 1 simplifies, Sec. 4 and Algorithm 1 are the reference, and we will redraw the figure to match.
  • Wrong references are corrected: LeDex had the wrong authors and title; ReCode had the wrong arXiv id and now cites the ACL 2026 version; APPS and Auer et al. had wrong author initials; S* is also corrected. The incomplete MCTS and contamination entries are replaced with PG-TD, RethinkMCTS and Riddell et al.
  • We also removed an appendix that did not contain an actual error analysis.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.