  Program synthesis aims to create accurate, executable programs from problem
specifications, specifically from natural language descriptions in our context.
Recent studies have leveraged the power of reinforcement learning (RL) in
conjunction with large language models (LLMs), significantly enhancing code
generation capabilities. The application of RL focuses on directly optimizing
for functional correctness, offering an advantage over conventional supervised
methods. Despite policy-based RL methods dominating the literature on RL for
program synthesis, the nature of program synthesis tasks hints at a natural
alignment with value-based methods. This stems from the rich collection of
off-policy programs, including those developed by human programmers and also
historical samples, coupled with the straightforward verification of generated
programs through automated unit testing, meaning rewards are easy to obtain.
Diverging from the dominant use of policy-based algorithms, our work explores
the feasibility of value-based approaches, leading to the development of our
$\mathcal{B}$-Coder (pronounced Bellman coder). Yet, training value-based
methods presents challenges due to the enormous search space inherent to
program synthesis. To this end, we introduce an initialization protocol for RL
agents utilizing pre-trained LMs and a conservative Bellman operator to reduce
training complexities. Moreover, we demonstrate how to leverage the learned
value functions as a dual strategy to post-process generated programs. Our
empirical evaluations demonstrated $\mathcal{B}$-Coder's capability in
achieving state-of-the-art performance when compared to policy-based methods.
Remarkably, this achievement is reached with minimal reward engineering effort,
highlighting the effectiveness of value-based RL, independent of reward
designs.
