Extracting Heuristics from Large Language Models for Reward Shaping in Reinforcement Learning

We thank the reviewer for their thoughtful comments and feedback, and that they find our idea novel and experiments to be comprehensive. We have tried addressing each of the concerns below:

$**Clarification on using LLM-generated plans (W1):**$ Recall from lines 81-92 in the paper’s Introduction section where we talk about the underlying MDP to have stochastic transitions. In the deterministic abstraction case, we can not use the plan generated by the LLM to solve the task. Similarly, in the hierarchical abstraction case, the LLM-generated plan only consists of the right sequence of subgoals the agent has to achieve. Hence, in both cases, we construct the reward shaping function using the LLM-generated plans to accelerate the RL agent’s training for the downstream tasks.

$**Clarification on non-deterministic environments (W2):**$ We do mention this in the Introduction section of the work (see response to W1), but have also reiterated this point for readers’ understanding again in the experiment section in lines 346 and 353..

$**High Standard Deviation in Figure 4 (W3):**$ We double-checked our plots to find that there indeed was an error during the plot generation step in our results. We have updated our plots to fix the issue as can be seen in Figure 4 on page 9.

$**Efforts behind prompt engineering (W4):**$ Since we aim to obtain the reward shaping plan from the LLM on the deterministic MDP, it becomes important to include information on the state and action space along with a description of the environment as part of the input prompt - a common practice in several existing works [3,4,5,6]. Moreover, we would like to highlight that this assumption is relaxed in the hierarchical MDP abstraction case where we prompt the LLM with the PDDL file which has been generated by the LLM itself [2], thereby reducing the human prompt effort significantly. An optimal policy can be helpful to construct the intended reward shaping function, as pointed out by the reviewer, but our work specifically looks at investigating the extent to which we can use off-the-shelf LLMs to provide any useful guidance for the task at hand. Note, that this can particularly be useful for environments which consist of an exponentially large state/action space where obtaining an optimal policy can be computationally expensive.

$**Clarification on paper’s taxonomy (W5):**$ Our work does not intend to pose a dichotomy between a deterministic and a hierarchical MDP setup, but aims to study these two possible MDP abstractions for a downstream RL task which has sparse-reward and stochastic transitions. To further clarify this point and take the reviewer’s suggestion into consideration, we have updated the description of these two cases in our Introduction section in lines 93-95.

We have tried addressing each of the questions below:

$**Clarification on Table 1 results (Q1):**$ We do not intend to compare different LLMs but aim to show how effectively we can obtain a plan using the different LLMs with and without the presence of a verifier in Table 1 and 2. We average across 3 runs, however, note that we simply need one plan from the LLM for any given domain to construct the reward shaping function. Furthermore, we point the reviewer to the answer above to W2 to clarify the point on the non-determinism in the environments’ transitions.

$**Choice of hyperparameters (Q2):**$ We ask the reviewer to check the attached zip file in our submission which contains the code and the appendix to our work. The hyperparameters have been chosen to be the same as our baseline in [1] and we have included these in Appendix C.2.

$**Example prompts and clarification on Appendix (Q3):**$ We would like to point the reviewer to Section D of the appendix in the attached zip directory for all the prompts that we use in this work. We would be happy to answer any further questions regarding the examples.

[1] Guan, Lin, Sarath Sreedharan, and Subbarao Kambhampati. "Leveraging approximate symbolic models for reinforcement learning via skill diversity." International Conference on Machine Learning. PMLR, 2022.

[2] Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pretrained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081–79094, 2023.

[3] Wang, Guanzhi, et al. "Voyager: An open-ended embodied agent with large language models." arXiv preprint arXiv:2305.16291 (2023).

[4] Ma, Yecheng Jason, et al. "Eureka: Human-level reward design via coding large language models." arXiv preprint arXiv:2310.12931 (2023).

[5] Yao, Shunyu, et al. "React: Synergizing reasoning and acting in language models." arXiv preprint arXiv:2210.03629 (2022).

[6] Shinn, Noah, et al. "Reflexion: Language agents with verbal reinforcement learning." Advances in Neural Information Processing Systems 36 (2024).

Thank you for the feedback! We would like to clarify the following points:

1. We do not assume access to the full PDDL specification for the hierarchical case for the following two reasons:

   A) It is very common that a problem can not (or is challenging to) be fully represented with PDDL, for example problems such as in motion planning or problems that have stochastic dynamics (such as ours too).

   B) The more complicated a PDDL is, the more likely that the model can be inaccurate or incomplete [1], and even humans can make mistakes as has also been noted in [2]. LLMs will naturally be more prone to errors.

While the above two points are well known, here our standpoint is that reward shaping can circumvent many of the challenges posed above. For our hierarchical case, the PDDL specification only consists of sub-goals that the downstream agent needs to achieve. Our results for RQ2 also indicate that the RL agent is able to perform better than the baseline Q-learning even when a partial set of subgoals is present in the PDDL specification.

Moreover, the underlying MDP is stochastic even in the hierarchical case. For a classical planner to compute an optimal policy for the underlying MDP, a human (domain expert) or some other information source needs to provide a complete PDDL specification taking stochastic transitions into account, which is not trivial.

2. The idea behind using concise PDDL specifications with respect to the underlying MDP is that we are able to generate a reward shaping function using this LLM-generated specification. Naturally, having a more complex PDDL specification that consists of the entire low-level action space and state constraints (as preconditions and effects) will lead to a stronger reward shaping function that can potentially guide the RL agent at every step. However, it is not feasible to obtain such complex PDDL specifications other than asking from domain experts as has been stated above.

We hope our clarification is helpful in understanding the hierarchical abstraction setting. We would be happy to answer any further questions!

[1] Guan, Lin, Sarath Sreedharan, and Subbarao Kambhampati. "Leveraging approximate symbolic models for reinforcement learning via skill diversity." International Conference on Machine Learning. PMLR, 2022.

[2] Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pretrained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081–79094, 2023.

We thank the reviewer for their thoughtful comments and feedback, and that they find our idea promising. We have tried addressing each of the concerns below:

$**Contribution novelty (W1):**$ To reiterate on the claims of our work, we would like to highlight from lines 102-112 in the paper that we aim to study the effectiveness of using LLMs for solving simple problem abstractions of downstream sparse-reward RL problems with stochastic transitions. While we obtain a PDDL model of the underlying MDP problem as in [1] and show the effectiveness of the guidance obtained using LLMs with and without a verifier, we go further and show a novel approach for utilizing these LLM-generated plans on abstract MDPs to construct reward shaping function for boosting the sample efficiency of downstream RL agents.

$**Extraction of PDDL models (W2):**$ We regret the confusion regarding the PDDL extraction step as we replicate the steps used in [1]. Furthermore, we would like to point the reviewer to the example prompts in Appendix section D for reference. We would be happy to answer any further clarifications.

$**Scalability (W3 and W4):**$ We restrict the current scope of the work to discrete action space environments with stochastic transitions and present a comprehensive analysis on multiple environments using two different MDP abstractions. However, we believe that extending our reward shaping work to partially observable action space environments can be a valuable future extension. For example, our hierarchical abstraction, which requires LLMs to output the right sequence of subgoals that the agent has to achieve, can be easily utilized. Similar to the discrete action space experiments shown for Mario, Minecraft, and the Household environment in our work, the RL agent can learn a policy that follows the correct sequence of subgoals using shaped rewards in a partially observable environment too. We have also included this point in our Discussion section in lines 510-515.

$**Clarification on Mario and Minecraft (W5):**$ We do point the reviewer to lines 409-413 where we have cited the relevant work from where we adopt the environments and the baselines.

$**Comparison to other LLM-enhanced RL methods (W6):**$ Due to the fundamental differences in our approach, we do not consider baseline from the works that we mention in the Related Works section. None of the existing works utilize LLMs to obtain guidance for an underlying sparse-reward stochastic environment on which we intend to boost the RL agent’s sample efficiency.

$**Clarification on LLM inference costs (W7):**$ The total cost to complete all our LLM experiments (with multiple runs) for Table 1 and Table 2 results combined was below $20.

$**Effort behind prompt designs (W8):**$ Since we aim to obtain the reward shaping plan from the LLM on the deterministic MDP, it becomes important to include information on the state and action space along with a description of the environment as part of the input prompt - a common practice in several popular works [3, 4, 5, 6]. Moreover, we would like to highlight that this assumption is relaxed in the hierarchical MDP abstraction case where we prompt the LLM with the PDDL file which has been generated by the LLM itself [1], thereby reducing the human prompt effort significantly.

$**Limitations of the proposed approach (W9):**$ We have highlighted some of the important limitations and trade-offs to be considered for our approach in the Discussion section 5.4. We would be happy to answer any further clarifications.

$**Q-learning algorithm for RQ 2.2 (W10):**$ For the sake of uniform comparisons in our empirical setting, we use the algorithm exactly as in our baseline in [2].

[1] Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pretrained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081–79094, 2023.

[2] Guan, Lin, Sarath Sreedharan, and Subbarao Kambhampati. "Leveraging approximate symbolic models for reinforcement learning via skill diversity." International Conference on Machine Learning. PMLR, 2022.

[3] Wang, Guanzhi, et al. "Voyager: An open-ended embodied agent with large language models." arXiv preprint arXiv:2305.16291 (2023).

[4] Ma, Yecheng Jason, et al. "Eureka: Human-level reward design via coding large language models." arXiv preprint arXiv:2310.12931 (2023).

[5] Yao, Shunyu, et al. "React: Synergizing reasoning and acting in language models." arXiv preprint arXiv:2210.03629 (2022).

[6] Shinn, Noah, et al. "Reflexion: Language agents with verbal reinforcement learning." Advances in Neural Information Processing Systems 36 (2024).

We thank the reviewer for their thoughtful comments and feedback, and that they find our paper easy to follow. We have tried addressing each of the concerns below:

$**Comparison to referenced paper (W1):**$ A very important difference between the referenced work by Zhang et al. and our work is in the problem setting since we are trying to focus on sparse-reward problems with stochastic transitions. Due to a stochastic transition function in the underlying MDP, the problem of sample inefficiency is pronounced. Hence, our solution involves constructing an abstraction of this underlying MDP where we study the use of LLMs to extract shaped rewards. Nevertheless, since this work also falls under the direction of using LLMs for RL problems, we apologize for having missed this and have now included it in our Related Works section in line 135 where we talk about other RL works that focus on LLM-based guidance.

$**Assumptions behind constructing the verifier (W2):**$ We would like to highlight that in the hierarchical abstraction case, the PDDL (symbolic) model of the task is teased out of the LLM, this assumption behind the verifier is relaxed (as mentioned in lines 511-520 in the paper). Note, that this is dependent on how expensive it may be to obtain a domain model for the task at hand, and if there are any constraints on the RL agent's training stage. Our results consistently show that having a verifier in the loop can significantly improve the quality of the obtained heuristics which can boost RL agent’s sample efficiency.

We have tried addressing each of the questions below:

$**Extending approach to complex action-space environments (Q1):**$ We restrict the current scope of the work to discrete action space environments with stochastic transitions and present a comprehensive analysis on multiple environments using two different MDP abstractions. However, we believe that extending our reward shaping work to continuous action space environments can be a valuable future extension. For example, our hierarchical abstraction, which requires LLMs to output the right sequence of subgoals that the agent has to achieve, can be easily utilized for continuous action spaces. Similar to the discrete action space experiments shown for Mario, Minecraft, and the Household environment in our work, the RL agent can learn a policy that follows the correct sequence of subgoals using shaped rewards in a continuous environment too. We have also included this point in our Discussion sub-section in lines 510-515.

$**Subgoal verification (Q2):**$ Currently, we generate the PDDL files by prompting the LLM, as has been proposed in [1], where the work relies on the assumption that LLMs can rely on their background training data for generating the subgoals for respective domains. To ensure that the subgoal has been reached, we can either extract that information from the environment state as has been done in our baseline [2] or train binary classifiers as has been done in [3], or even use state-of-the-art VLMs [4].

[1] Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pretrained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081–79094, 2023.

[2] Guan, Lin, Sarath Sreedharan, and Subbarao Kambhampati. "Leveraging approximate symbolic models for reinforcement learning via skill diversity." International Conference on Machine Learning. PMLR, 2022.

[3] Mirchandani, Suvir, Siddharth Karamcheti, and Dorsa Sadigh. "Ella: Exploration through learned language abstraction." Advances in neural information processing systems 34 (2021): 29529-29540.

[4] Du, Yuqing, et al. "Vision-language models as success detectors." arXiv preprint arXiv:2303.07280 (2023).

We thank the reviewer for their thoughtful comments and feedback, and that they find our algorithm easy to understand and the experiment section comprehensive. We have tried addressing each of the concerns below:

$**Prompting and paper’s claims (W1):**$ Our primary contributions in this work do not include claiming any novelty regarding the prompting step or the check made using the verifier for legal moves. As stated in lines 102-112 of the paper, we focus on studying how well LLMs can solve simple problem abstractions of sparse-reward RL tasks with stochastic transitions. We are actually glad that the prompting step is simple enough, as verified by the reviewer.

$**Clarifications on writing and figure (W2):**$ Once we have the desired <state, action> pairs (in the deterministic abstraction setting) or the desired <state>s (in the hierarchical abstraction setting) from prompting the LLM, we simply store this information in Step II (as shown in Figure 1). During the RL training process, we check for these desired <state, action> pairs or <state>s in the respective settings and reward shape those transitions. Hence, we did not show an arrow from the replay buffer in Figure 1.

$**Clarification on experiment results (W3):**$ Recall from lines 81-92 in the paper’s Introduction section, that we talk about the underlying MDP to have stochastic transitions. In the deterministic abstraction case, we can not use the plan generated by the LLM to solve the task. Similarly, in the hierarchical abstraction case, the LLM-generated plan only consists of the right sequence of subgoals the agent has to achieve. Hence, in both cases, we construct the reward shaping function using the LLM-generated plans to accelerate the RL agent’s training for the downstream tasks.

About the paper the reviewer referenced, it talks about using LLMs to generate linguistic rules that can be helpful to solve two-player games. The experiments in the paper include two-player communication, maze, and image-generation tasks. However, we do not see any experiments on the BabyAI domain in the current arxiv version of the work (https://arxiv.org/pdf/2405.04118). Moreover, the problem setup is very different from ours where the referenced work aims to generate interpretable (and thus, linguistic) rules that allow for solving the two-player communication tasks. We focus on the single-agent setting where the objective is to accelerate RL agent’s training on a sparse-reward problem with stochastic transitions. We would be happy to answer any further questions the reviewer may have regarding the setup or comparisons between the two works, if we missed anything. Moreover, since this work also falls under the overall direction of using LLMs for decision-making problems, we have included this work in our Related Work section in line 135 where we talk about other RL works that focus on LLM-based guidance.