I thank the authors for their exhaustive answers to my questions, as well as their receptiveness to my other suggestions for improving the paper.

I can fully see their point about the unavailability of test case-based rewards in a realistic deployment setting. Still, I would suggest that an evaluation of their method with filtering based on environmental rewards $r(s,a)$ (or anyway the same reward function used for training it and carry out policy improvement) be added at least to the appendix. It might not be representative of a realistic deployment situation, but in my opinion it would be an insightful sanity check, also for any future readers.

Also, have the authors already posted the revised version of their paper? I can still only see the initial version. I would like to read the revised one before I make any decisions on whether to update my score.

Thank you very much for your time in reviewing our work and your valuable comments! We are glad that you found our approach novel and elegant! We are enthusiastic about improving our paper by incorporating your constructive suggestions.

Weaknesses and Main Question

its comparison with baselines gives mixed results: in some cases, it does not actually come out on top. This contradicts the authors' claim that value-based method should be more suited to code generation

We believe the mixed results are largely influenced by the degree of reward engineering involved. Our approach intentionally uses minimal reward engineering, as shown in our Eq. (2), while the baselines use quite complex reward designs. A comparison is available in Table 5, Appendix C. Ablation studies in baseline papers, such as Table 2 in CodeRL, Figure 3(a) in PPOCoder, and Table 5 in RLTF, demonstrate that their reward designs contribute significantly to the performance.

We were restraint on reward engineering because we seek to offer a clearer discussion on the design of value-based methods without blending in too much reward factors. This trade-off was made to enhance our focus on algorithmic insights. As the reviewer has highlighted, the fact that all baseline methods are policy-based adds value to our initial attempt of value-based training.

Main question and concern: why do the authors use a filtering procedure at evaluation time based on a different reward model $\tilde{r}(s, a)$ than the environmental reward $r(s, a)$ they use for training? Given that the real reward $r$ can be easily and cheaply computed

We would like to response to the main question first, to clarify our choice of a different reward function $\tilde{r}(s, a)$ instead of the ground truth reward.

The primary reason is the availability of test cases, which provide true rewards. During model training or evaluation, test cases are often available and required, as both training and test datasets are typically constructed with them. This context is what we meant by `real reward $r$ can be easily and cheaply computed'. However, in practical scenarios, test cases are not always available, making it challenging to obtain real rewards.

An example scenario. When deploying a fine-tuned model for end-user applications, users often provide natural language descriptions of their needs but may not include test cases (which can also be challenging for beginners or casual users). This situation is quite common and real rewards are unobtainable.

$\tilde{r}$ in such scenarios. Our reward model $\tilde{r}$ doesn't require test cases from end users, and hence is applicable. Moreover, in many applications, such as GitHub Copilot, the model must offer a single best response, not a range of options. Thus, the ability to rank programs without test cases (true rewards) is not only realistic but also advantageous.

Additional benefits. As discussed in Section 4, $\tilde{r}$ requires no additional training and adds minimal computational overhead, as $Q$ and $V$ are already evaluated during program generation. In contrast, the critic sampling strategy used in CodeRL and RLTF requires (i) training a separate repair model and (2) available test cases (i.e. true rewards) for post-processing, which is less desired due to aforementioned reasons.

Remark on training with $\tilde{r}$. Recall that our reward model $\tilde{r}$ is obtained from $Q$ using Eq (19), without additional training. Using $\tilde{r}$ to train $Q$ from outset is in fact creating a chicken-and-egg problem. Besides, complex reward engineering during training is also something we tried to avoid.

We hope our explanation addresses the reviewer's major concern and clarifies our choice.

The authors filter programs at evaluation time using a different reward than the one used during training. This makes it hard to interpret their performance numbers. Could it be the filtering that is mostly responsible for them?

We hope our response to the main question helps address the concern about the use of a different reward. Ranking indeed improves performance as we expected. However, both initialization and conservative updates contribute significantly to the final performance. The comparison with CodeRL and RLTF with post-processing, i.e. critic sampling, is also available in Table 2. And we would like to highlight that our reward ranking is a more realistic post-processing strategy as explained above, and our model was trained with minimal reward designs.

Thank you for your prompt response and further suggestions.

Still, I would suggest that an evaluation of their method with filtering based on environmental rewards $r(s, a)$ be added at least to the appendix.

Certainly, we will carry out the suggested experiments and include them in the Appendix in future revision.

Also, have the authors already posted the revised version of their paper? I can still only see the initial version.

We are delighted to upload an initial revision as per the reviewer's request. In this preliminary revision, we have made the majority of the changes suggested by all the reviewers. The changes have been highlighted in blue. Specifically, we have made the following adjustments in line with Reviewer 3d3T's recommendations:

1. ``The paper has a bit of an idiosyncratic structure, with e.g. a whole section dedicated only to the reward filtering at evaluation time, a very small Related Work section, and no outline of the paper's contents in the introduction, which makes it a bit hard to read.''

   • The introduction and related work sections have been revised for a more balanced structure.

   • The reward section has been restructured as a subsection under our methodology section. To optimize space within this subsection, certain background paragraphs have been relocated to Appendix C, while other, less crucial details have been moved to Appendix E.

2. ``the authors do not elaborate on it. The authors should either: Justify this choice. ...''

   • In Section 4.5, we added a paragraph to further elaborate on the deployment setting and to justify our choice.

3. ``Can the authors outline their paper's content and structure at the end of the intro?''

   • We have added an outline of our paper's structure to the end of our introduction section.

4. ``In figure 3 (now figure 2 after revision), it would be helpful to explicitly define what and $\ell$ and $p$ stand for''

   • The captions have been updated for explicit definitions.

5. ``Why is the Nucleus Sampling outlined at the end of section 3? In my opinion it would make more sense to have in section 5''

   • The sampling details have been relocated to Section 5.

6. ``It would be helpful if the authors defined (e.g. in a caption) what "Intro", "Inter", "Comp", and "All", mean in tables 1 and 2.''

   • The caption of Table 1 has been updated. While Table 2 remains unchanged at present, we plan to enhance our writing for conciseness, creating space for an updated caption for Table 2.

7. ``The study on generalisation of the reward model (notwithstanding my concerns on its use, detailed above) would better be moved to an appendix.''

   • We have reduced the length of the 'reward model' subsection and moved some less important content to Appendix, to accommodate the reviewer's suggestions, which allowed us to maintain the 'reward model generalization' experiments in their current place. We hope that the reviewer finds this arrangement sensible after our clarification on choice of $\tilde{r}$. However, if the reviewer still believes these experiments would be better suited to the appendix, we are happy to make those revisions.

Thank you once again for your thorough review and valuable insights! We hope that this initial revision adequately addresses the reviewer's concerns regarding the paper's overall structure and flow, even though it may still contain typographical and grammatical errors. We are committed to continuously refining our paper to improve its presentation.

Thank you very much for your time in reviewing our work and for your positive assessment! We are glad that you found our work original and of very high quality, and our paper well-written! We are enthusiastic about improving our paper by incorporating your valuable comments.

Figure 2.

We apologize for any ambiguity and inconsistency in the figure. The extended training of the other two veins was to demonstrate the challenges of value-based training, even when allowing more training episodes. Our evaluation points were randomly selected, leading to the varying distances between points. Despite these factors, we believed the overall trend was clear enough to demonstrate the impact of different components.

is it true that the reward model coming for free in section 4 is possible for any Bellman operator? what are the preconditions necessary for this?

Yes, this is indeed possible for any operator that is a contraction. Being a contraction ensures a unique fixed point $Q$ upon convergence, which in turn allows an one-to-one correspondence with the reward function $\tilde{r}$. We will amend the comments preceding Proposition 3.1 to more clearly indicate that the property of being a contraction is a sufficient condition for Proposition 4.1.

The related work paragraph should be renamed to something more precise

We certainly agree with the reviewer's point that the name ``related work'' is not quite fitting. We will rename it, for example, to ''RL in sequence generation'' or ''RL vs supervised fine-tuning''.

how does AlphaZero relate to the taxonomy of Figure 1? Isn't AlphaZero pretty much the same approach, but with all on-policy data?

Thank you for pointing out this aspect. The statement from the AlphaZero paper: ``Self-play games are always generated by using the latest parameters for this neural network'', initially suggested to us the exclusive use of on-policy data. However, further examination led us to a pseudocode in their supplementary materials [1]. The code snippet suggests that they use a replay buffer, which is designed to re-use historical data in RL.

For a training step $j$, data generated by $\pi_i$, where $i < j$, are also considered as off-policy data because they do not follow the state-action distribution $\rho_{\pi_j}(s, a)$ of the current policy $\pi_j$. Therefore, we believe that AlphaZero also uses a substantial amount of off-policy data, through experience replay.

def train_network(config: AlphaZeroConfig, storage: SharedStorage,
                  replay_buffer: ReplayBuffer):
  network = Network()
  optimizer = tf.train.MomentumOptimizer(config.learning_rate_schedule,
                                         config.momentum)
  for i in range(config.training_steps):
    if i % config.checkpoint_interval == 0:
      storage.save_network(i, network)
    batch = replay_buffer.sample_batch()
    update_weights(optimizer, network, batch, config.weight_decay)
  storage.save_network(config.training_steps, network)

[1] AlphaZero Supplementary Materials. https://www.science.org/doi/10.1126/science.aar6404#supplementary-materials

A demonstrative experiment.

• An illustrative MDP. (An illustrative figure of this MDP can be found anonymously here.) Consider a chain MDP, where there are $n+1$ states $s_0, \ldots, s_n$ with two actions LEFT and RIGHT, where LEFT at $s_i$ proceed to the previous state $s_{i-1}$ with reward $r=1$, and RIGHT always proceed to the next state with $r=-1$ except moving to the terminal state $s_n$, which has $r = k\times H$, where $k \geq 2$ and $H$ is the episode length. The optimal strategy should be always choosing RIGHT.

• Dataset. We collect a dataset $D$ with an uniform policy with $\pi(\text{LEFT}|s) = \pi(\text{RIGHT}|s) = 0.5$ for all $s$. We will next use this dataset to simulate two scenarios: (1) dataset is on-policy: we optimize an uniform policy using this dataset, corresponding to optimizing an policy using on-policy dataset (as both are uniform); (2) we optimize a better policy $\pi_{new}(\text{RIGHT}|s)=0.75$ using this uniform dataset, corresponding to optimizing an (new/improved) policy using old/historical dataset.

• Training results. (The training curves can be found anonymously here.) (1) data is on-policy: Using $D$ to fine-tune an uniform policy, both PG and ours are able to improve the performance. (2) data is off-policy: We use $D$ to fine-tune a policy of $\pi_{new}(\text{RIGHT}|s)=0.75$. While the canonical PG loss is $-\mathbb{E}_{\color{blue} \tau\sim\pi} [R(\tau)]$, reusing the old data (in program synthesis works) are often done by directly using the dataset's empirical distribution and the pseudo loss [7], i.e.

  $L(\pi) = -\frac{1}{|D| H}\sum_{\color{blue} \tau \in D}\sum_{t=1}^H [\log \pi(a_t|s_t) R(\tau_{\geq t})]$.

  PG only performs better than the dataset average performance but lower than the average returns of $\pi_{new}$, while ours could improves from $\pi_{new}$.

• Remark on this observation. For a pair $(s, a)$, let's first define ''dataset average returns'', $\overline{R}(s, a) := \frac{1}{|D| H} \sum_{\tau\sim D} \sum_{t=1}^H [ \mathbb{I}(s_t=s) \mathbb{I}(a_t=a) R(\tau_{\geq t})]$, where $\mathbb{I}$ is an indicator function. In the case (2) described above, for a state $s$, optimizing $L(\pi)$ is equivalent to finding $\arg\max_a \overline{R}(s, a)$. It in fact has nothing to do with the initial policy's performance $J(\pi_{new})$ but is only determined by the dataset $D$, i.e. finding the actions with higher ``dataset average returns''.

  Figure (anonymously available here) validates that PG consistently converges to the actions with higher average ``dataset average returns'' $\overline{R}(s, a)$, instead of the optimal action, even when initialized from a near-optimal policy $\pi_{new}$. This demonstrates that training a new/improved policy using old/historical data can lead to a decrease in policy performance (which also explains the observation found by PPOCoder).

Thank you very much for your time in reviewing our work and for your positive assessment! We are glad that you found our work of good quality, and showing the feasibility of value-based approach is a great merit. We are enthusiastic about improving our paper by incorporating your valuable comments.

We would like to address the clarity and significance questions in a somewhat mixed order, as beginning with the technical definitions would help us better explain our motivations. We outline our responses as follows,

1. Our response to (a) clarifies the technical distinctions between (on-policy) policy-based and (off-policy) value-based methods, highlighting the data inefficiency of the former due to their inability to reuse historical data, a limitation rooted in their technical nature.

2. Our response to (b) lists empirical evidence from RL literature and public RL benchmarks.

3. Our response to (c) provides a demonstrative example to validate the intuition discussed in (a).

4. The rest are responses to the reviewer's other concerns.

(a) I feel the paper is overboard with definition and philosophy of "what is policy-based" and "what is value-based / RL". I believe these things have a very technical definition that the community can all agree with.

As pointed out by the reviewer, we do realize that our description was quite verbal, which could create ambiguity and confusion. Our intended focus is on the algorithm's capability to re-use previously generated data, as being unable to reuse old/historical data (costly to collect) is very inefficient. Mathematically, this can be characterized by determining whether the objective function requires data to be drawn from the distribution induced by the current policy, as demonstrated in the following examples:

where $R(\cdot)$ is cumulative trajectory-wise returns, $k$ denotes the current gradient/update step, $\tau \sim \pi$ or $\tau \sim \pi_k$ indicates the trajectories $\tau$ are rollouts collected by the current policy $\pi$ or $\pi_k$, whereas $D$ could be an arbitrary dataset.

This technical difference was not precisely reflected in our current writing, as commented by the reviewer. We are gratefully for the reviewer's suggestion on technical definitions, which will largely help us to improve our paper's clarity.

Remarks on practical aspect. (on-policy) policy gradient methods, in principle, cannot reuse previously generated, as they won't follow the current policy's (state-action) distribution. This is undesirable as generating samples with Transformers are known to be expensive.

PPOCoder indeed has some discussion on this aspect. To briefly recap, they generate synthetic programs at $k=0$ (prior to fine-tuning), and subsequently fine-tune their model using both human and synthetic programs drawn from this mixed distribution. It was observed in PPOCoder (Figure 3(e)) that an increase in synthetic programs negatively impacts fine-tuning performance. This is partly because the mixed distribution doesn't align with the fine-tuned policy's state-action distribution.

However, with more data, an ideal objective is generally expected to either improve or at least maintain a policy's performance, not decrease it. In general, the use of (growing) historical off-policy data is the key to the better sample efficiency observed in off-policy value-based methods.

I could think of many other benefits of having a value function, for instance, sometimes people might want a top-k ranked programs, which could be tricky to do based on only policy, but very intuitive with a value based model.

This is indeed one of our considerations. The details, of selecting top-$k$ programs by value functions, are given in Section 4. In addition, for instance, one may also derive beam search strategy that maximizes values rather than likelihood and we certainly agree with the reviewer that having a value function create further opportunities.

Defining program synthesis as "generating program from natural language" is imprecise

Thank you for pointing it out. We realize that we were narrowly focused in terms of program synthesis definition, because we were somewhat limited to the specific APPS dataset. It is very true that the program synthesis problem should be more general. We are delighted to revise our definition to be more accurate and encompassing, in line with the reviewer's suggestion.

Time to take sample?

We take 5 problems from APPS test set (id 0 - 4) as examples and sampled 1000 programs for each, using one RTX 4090 24GB graphics card, with maximum batch sizes that do not create OOM errors. The table below shows the sampling time (in secs) per 1000 programs, in the format of mean$\pm$std. Our method takes approximately 1.7 to 2.0 times longer to sample.

Remark on faster sampling. While we originally proposed using $Q$ as logits for sampling, it is also feasible to use the advantage $A$ as logits for sampling, especially when the goal is to generate as many outputs as possible without evaluating $Q$ and $V$ values. This would not require evaluating $V$, and therefore, we would expect similar sampling times. Under the same setting, sampling with advantage $A$ takes $275.79$ seconds and $322.78$ seconds for temperatures of $0.4$ and $1.0$, respectively, which are similar to CodeRL as we expected.

[1] Nachum, Ofir, et al. "Bridging the gap between value and policy based reinforcement learning." Advances in neural information processing systems 30 (2017).

[2] Gu, Shixiang, et al. "Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic." International Conference on Learning Representations. 2016

[3] Haarnoja, Tuomas, et al. "Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor." International conference on machine learning. PMLR, 2018.

[4] Fujimoto, Scott, Herke Hoof, and David Meger. "Addressing function approximation error in actor-critic methods." International conference on machine learning. PMLR, 2018.

[5] Burda, Yuri, et al. "Exploration by random network distillation." Seventh International Conference on Learning Representations. 2019.

[6] Harutyunyan, Anna, et al. "Hindsight credit assignment." Advances in neural information processing systems 32 (2019).

[7] https://rail.eecs.berkeley.edu/deeprlcourse/deeprlcourse/static/slides/lec-5.pdf

Thank you very much for your time in reviewing our work and for your positive assessment! We are glad that you found our approach both creative and impressive! We are enthusiastic about improving our paper by incorporating your valuable comments.

2.1 Policy: should say "assigns an action from the set $\Delta(\mathcal{A})$" and generally this notation here needs checking.

Thank you for bringing this to our attention. We noticed that our notation was indeed inconsistent. In the statement ``assigns an action distribution $\Delta(\mathcal{A})$ ..., meaning predicting a token $\hat{w}_t$'', the first part refers to a distribution over actions, while the latter suggests a single token. We'll revise our notation accordingly to ensure better clarity and consistency.

In figure 2, why is zero training iterations the best? anyway this is a nice ablation / teaser for the paper.

We hypothesize that it is because the initial checkpoint has been already fine-tuned on the training set, hence having a good performance. Nonetheless, as the reviewer pointed out, we believe it highlights the difficulty of value-based training and the necessity of the proposed components.

General question: since you sample a softened $Q$ as your policy, you could actually apply policy gradients as well. What are the connections here? Could you combine your scheme with a policy gradient type of update?

As our focus was on value-based learning, we did not incorporate a policy gradient loss in our framework. However, we believe this could be a promising and exciting direction, as one may benefit from both the robustness of policy optimization and sample-efficiency of value-based learning, with careful designs.

Can PG loss be combined? Yes, as suggested by the reviewer, it is certainly feasible to optimize $Q$-function with policy gradient objective through an energy-based policy, by computing $\nabla_\theta \log \pi_Q(a|s) = \nabla_\theta [Q_\theta(s, a)/\alpha - \log \sum_u \exp (Q_\theta(s, u)/\alpha)]$ (which is tractable due to a discrete vocabulary) and then plugging it into policy gradient.

Connection. This question leads us to an earlier work [1], which exactly explores the combination of policy-based and value-based learning, by leveraging energy-based policies. This could also be considered as an actor-critic framework with a shared network ($s \to \text{shared net} \to Q \xrightarrow{\mathrm{softmax}} \pi$ ), which is feasible when $\mathcal{A}$ is discrete. And the shared network can be optimized by the combination of policy gradient and temporal difference losses, applied to $\pi$ and $Q$ respectively.

We are thankful to the reviewer for this inspirational question, which creates an exciting opportunity. And we will include further discussion on this combination, along with relevant works, into our revision.

[1] O'Donoghue, Brendan, et al. "Combining policy gradient and Q-learning." International Conference on Learning Representations. 2016."