How Can LLM Guide RL? A Value-Based Approach

## Abstract

Abstract Reinforcement learning (RL) has become the de facto standard practice for sequential decision-making problems by improving future acting policies with feedback. However, RL algorithms may require extensive trial-and-error interactions to collect useful feedback for improvement. On the other hand, recent developments in large language models (LLMs) have showcased impressive capabilities in language understanding and generation, yet they fall short in exploration and self-improvement capabilities for planning tasks, lacking the ability to autonomously refine their responses based on feedback. Therefore, in this paper, we study how the policy prior provided by the LLM can enhance the sample efficiency of RL algorithms. Specifically, we develop an algorithm named 𝙻𝙸𝙽𝚅𝙸𝚃 𝙻𝙸𝙽𝚅𝙸𝚃 \mathtt{LINVIT} typewriter_LINVIT that incorporates LLM guidance as a regularization factor in value-based RL, leading to significant reductions in the amount of data needed for learning, particularly when the difference between the ideal policy and the LLM-informed policy is small, which suggests that the initial policy is close to optimal, reducing the need for further exploration. Additionally, we present a practical algorithm 𝚂𝙻𝙸𝙽𝚅𝙸𝚃 𝚂𝙻𝙸𝙽𝚅𝙸𝚃 \mathtt{SLINVIT} typewriter_SLINVIT that simplifies the construction of the value function and employs sub-goals to reduce the search complexity. Our experiments across three interactive environments ALFWorld, InterCode, and BlocksWorld demonstrate that our method achieves state-of-the-art success rates and also surpasses previous RL and LLM approaches in terms of sample efficiency. Our code is available at https://github.com/agentification/Language-Integrated-VI .

## 1 Introduction

Trained on the web-scale corpora, Large Language Models (LLMs) have exhibited emergent capabilities and seen tremendous success across various fields, such as code development (Chen et al., ; Roziere et al., ; Li et al., ) and theorem proving (Yang et al., ; Romera-Paredes et al., ). The recent advances in robotics (Huang et al., ; Liang et al., ) and games (Wang et al., ; Yuan et al., ; Wang et al., ; Liu et al., ) further highlight the potential of LLMs to build effective agents in well-designed interactive environments.

However, the reasoning and planning abilities of LLMs, which are important metrics for intelligent agents, have been found to be inconsistent and often unreliable (Valmeekam et al., ; Mahowald et al., ; Huang et al., ; Pallagani et al., ). Besides, agents powered by LLMs tend to have limited abilities to explore different strategies, frequently defaulting to repeating established policies. This limitation becomes particularly pronounced in complex decision-making scenarios that LLMs are not specifically attuned to, resulting in significant difficulties in refining their strategies based on environmental feedback by reasoning the environment feedback based solely on its inherent capabilities (Valmeekam et al., ; Shinn et al., ; Ivanova, ; Zhang et al., ). On the contrary, Reinforcement Learning (RL) is a well-studied methodology for improving future acting policies with feedback. Unfortunately, improving from scratch without the guidance of prior knowledge, such as common sense, requires the RL agents to take a huge amount of random interactions to collect useful feedback, leading to poor sample efficiency and even failure in sparse-reward environments.

Figure: Figure 1: Illustration of the differences and the respective advantages, disadvantages of RL and LLM agents in an instance of the ALFWorld decision-making task. We propose an RL framework leveraging the LLM as a policy prior that gets the best of both worlds.
Refer to caption: x1.png

Hence, in this paper, we aim to tackle these issues and answer the following question:

*Can we improve the sample efficiency of Reinforcement Learning*

*with Large Language Models?*

Our primary objective is to develop an algorithm that is both theoretically robust and empirically effective, utilizing LLMs to enhance sample efficiency. Our pivotal insight is the utilization of LLMs to define a regularizer, as opposed to directly employing them in decision-making. Leveraging the properties of regularized-MDPs, we find that sample complexity can be significantly reduced when the LLM-provided policy closely aligns with the optimal policy. Moreover, our approach retains the capability to identify the optimal policy even in scenarios where the LLM policy falls short. An illustration comparing the standard RL algorithms, LLM agents, and the RL framework with LLM as a prior is shown in Figure 1. To demonstrate this concept, we introduce an algorithm named Language-INtegrated Value Iteration ($\mathtt{LINVIT}$), which shows a marked improvement in sample complexity, particularly when the Kullback-Leibler (KL) divergence between the optimal policy and the LLM policy is minimal.

We further present a practical algorithm called $\mathtt{SLINVIT}$ and empirically validate it in various benchmarks, including ALFWorld (Shridhar et al., ), the interactive coding environment InterCode (Yang et al., ), and the planning benchmark BlocksWorld (Valmeekam et al., ). Experimental results show that the proposed algorithm outperforms previous RL and LLM algorithms by a large margin, achieving higher success rates with fewer numbers of samples.

## 2 Background

#### Reinforcement Learning.

Consider the problem of learning to optimize a finite $H$-horizon Markov Decision Process (MDP) over repeated episodes of interaction. We denote by $\mathcal{S}$ and $\mathcal{A}$ the state and action space, respectively. When taking an action $a\in\mathcal{A}$ at a state $s\in\mathcal{S}$ at timestep $h$, the agent receives a reward $r_{h}(s,a)$ and the MDP transits to a new state $s^{\prime}$ according to $s^{\prime}\sim P_{h}^{*}(\cdot\mid s,a)$.

We aim to find a policy $\pi$ that maps a state to an action distribution to maximize the expected cumulative reward. We denote by $Q^{*}_{h}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ and $V^{*}_{h}:\mathcal{S}\rightarrow\mathbb{R}$ the state-action value function and the state value function associated with $\pi$, respectively, which are defined as follows,

$$ $\displaystyle Q^{*}_{h}(s,a)=r_{h}(s,a)+\sum_{s^{\prime}}P_{h}^{*}(s^{\prime} \mid s,a)V_{h+1}^{t}(s^{\prime}),\qquad V^{*}_{h}(s)=\sum_{a}\pi(a\mid s)Q^{*} _{h}(s,a),$ $$

where $s\in\mathcal{S}$, $a\in\mathcal{A}$. The objective of the decision-making problem is to maximize the state value at the initial timestep $V^{*}_{1}(s_{1})$, where $s_{1}\in\mathcal{S}$ is the initial state.

#### Decision-Making with LLMs.

To solve decision-making problems, one can prompt the LLM agent to generate action responses $\pi^{\mathrm{LLM}}_{h}(a\mid s)$ based on its state $s$, which consists of the observation-action history up to the current timestep $h$ in partially observable MDPs, or contains an additional reasoning step (Yao et al., ) in a chain-of-thought (Wei et al., ) manner. Unfortunately, without the domain knowledge of a specific task or environment, the LLM policy is hard to be optimal, especially when the planning problems have long horizons and the LLM lacks the necessary reasoning abilities. On the contrary, in this work, we explore another manner of leveraging the LLM policy as the prior (or regularization) in RL.

## 3 Using Language Model as a Policy Prior

In this section, we present an algorithm leveraging LLM to enhance sample efficiency. We begin by discussing the algorithm’s motivation, followed by a detailed explanation of its procedure.

Motivation. A simplistic approach to using Large Language Models (LLMs) in decision-making is directly applying the LLM-generated policy to target tasks. However, pretrained and fine-tuned on the static datasets, LLMs are not inherently attuned to the specific interactive environments of concern and are unable to modify their policies based on environmental feedback. Consequently, effectively leveraging LLM information for decision-making remains an unresolved challenge. Inspired by the property of entropy-regularized MDP (Neu et al., ), our approach employs the large language model as a supplemental regularizer within the original algorithm, rather than using it as the primary decision-making tool. This methodology significantly improves sample efficiency when the LLM’s policy is closely aligned with the optimal policy. Moreover, we can still identify the optimal policy for the original MDP even if the LLM’s policy is suboptimal.

Figure: Algorithm 1 Language-INtegrated Value Iteration($\mathtt{LINVIT}$)

With the above motivation, we propose a novel algorithm Language-INtegrated Value Iteration ($\mathtt{LINVIT}$), which is structured in three distinct steps as shown in Algorithm 1. Initially, we utilize the gathered data to estimate the transition model and calculate the uncertainty associated with our estimation. Subsequently, this estimator is employed to formulate both the optimistic and pessimistic regularized value functions. The final step involves leveraging these value functions to develop an exploration policy, which is then used to acquire additional data from the environment. Each of these steps is elaborated in detail as follows.

Model and Uncertainty Estimation. We estimate the transition model as follows. Let $n_{h}^{t}(s,a)$ denote the number of times the state-action pair $(s,a)$ has been visited at step $h$ during the first $t$ episodes, and let $n_{h}^{t}(s,a,s^{\prime})$ denotes the number of times the state-action-next-state triplet $(s,a,s^{\prime})$ at the same step and episode count.
Our dynamics estimator $P^{t}_{h}(s^{\prime}|s,a)$ is defined as $P^{t}_{h}(s^{\prime}|s,a)=n^{t}_{h}(s,a,s^{\prime})/n^{t}_{h}(s,a)$ if $n_{h}^{t}(s,a)>0$ and $P^{t}_{h}(s^{\prime}|s,a)\triangleq 1/S$ for all $s^{\prime}\in{\mathcal{S}}$ else. We then define the uncertainty quantifier $u_{h}^{t}$ by

$$ $\displaystyle u^{t}_{h}(s,a)$ $\displaystyle\triangleq\max\biggl{\{}2H,\sqrt{\frac{\log(4HTS^{2}A/\delta)}{n_ {h}^{t}(s,a)}}\biggr{\}}.$ (3.1) $$

Intuitively, the uncertainty quantifier $u^{t}_{h}$ is inversely related to the frequency of visits to a state-action pair; the less frequently a state-action pair is visited, the greater the value of $u^{t}_{h}$. This relationship means that $u^{t}_{h}$ effectively measures our uncertainty regarding each state-action pair, capturing the uncertainty of our estimation.

Regularized Value Functions. After estimating the transition model and the uncertainty, we compute the optimistic and the pessimistic regularized value function by

$$ $\displaystyle\overline{Q}_{h}^{t}(s,a)=\mathrm{clip}\bigl{\{}r_{h}(s,a)+\sum_{ s^{\prime}}P_{h}^{t}(s^{\prime}\mid s,a)\overline{V}_{h+1}^{t}(s^{\prime})+u^{ t}_{h}(s,a)\bigr{\}},$ $\displaystyle\overline{V}_{h}^{t}(s)=\max_{\pi\in\Delta_{A}}\Bigl{\{}\sum_{a} \pi(a|s)\overline{Q}_{h}^{t}(s)-\lambda{\mathrm{KL}}\bigl{(}\pi(\cdot\mid s)\| \pi^{\mathrm{LLM}}_{h}(\cdot\mid s)\bigr{)}\Bigr{\}},$ (3.2) $$

with $\overline{V}^{t}_{H+1}=\underline{V}^{t}_{H+1}=0$ by convention, and

$$ $\displaystyle\mathrm{clip}(x)=\min\Bigl{\{}\max\bigl{\{}x,0\bigr{\}},H\Bigr{\}}.$ $$

The definition of $\overline{Q}$ and $\overline{V}$ comprise three components: the expected reward, the uncertainty estimator, and the regularization defined via $\pi^{\mathrm{LLM}}$. It can be viewed as an optimistic estimation of the regularized value function. We similarly define $\underline{Q}$ and $\underline{V}$ as

$$ $\displaystyle\underline{Q}_{h}^{t}(s,a)=\mathrm{clip}\bigl{(}r_{h}(s,a)+\sum_{ s^{\prime}}P_{h}^{t}(s^{\prime}\mid s,a)\overline{V}_{h+1}^{t}(s^{\prime})-u^{ t}_{h}(s,a)\bigr{)},$ $\displaystyle\underline{V}_{h}^{t}(s)=\max_{\pi\in\Delta_{A}}\Bigl{\{}\sum_{a} \pi(a|s)\overline{Q}_{h}^{t}(s)-\lambda{\mathrm{KL}}\bigl{(}\pi(\cdot\mid s)\| \pi^{\mathrm{LLM}}_{h}(\cdot\mid s)\bigr{)}\Bigr{\}}.$ (3.3) $$

Similar to $\overline{Q}$ and $\overline{V}$, $\underline{Q}$ and $\underline{V}$ can be regarded as pessimistic estimations of the regularized value function. The primary distinction between $\underline{Q}$ and $\overline{Q}$ lies in the sign of the uncertainty estimator.

Sampling Policy. We explore the environment and collect data with $\pi^{t+1}=\{\pi^{t+1}_{h}\}_{h=1}^{H}$, which is defined as

$$ $\displaystyle\pi_{h}^{t}(\cdot\mid s)=\frac{1}{H}\cdot\mathbbm{1}\{a=\mathop{ \mathrm{argmax}}\overline{Q}^{t}_{h}(s,a)-\underline{Q}^{t}_{h}(s,a)\}+\frac{H -1}{H}\cdot\bar{\pi}_{h}^{t}(\cdot\mid s),$ (3.4) $$

where $\bar{\pi}_{h}^{t}(\cdot\mid s)=\mathop{\mathrm{argmax}}_{\pi\in\Delta_{A}}
\Bigl{\{}\sum_{a}\pi(a\mid s)\overline{Q}_{h}^{t}(s)-\lambda{\mathrm{KL}}\bigl
{(}\pi(\cdot\mid s)\|\pi^{\mathrm{LLM}}_{h}(\cdot\mid s)\bigr{)}\Bigr{\}}$.

Intuitively, the difference $\overline{Q}^{t}_{h}(s,a)-\underline{Q}^{t}_{h}(s,a)$ captures the uncertainty of the estimation of the regularized value function. As a result, the policy $\pi_{h}^{t}$ is designed to act predominantly as a greedy policy concerning the optimistic regularized value function, doing so with a probability of $1-1/H$. Conversely, with a probability of $1/H$, it opts for the action associated with the greatest uncertainty. This approach ensures a balance between exploiting known rewards and exploring actions with higher uncertainty to refine the value function estimation.

## 4 Experiments

In this section, we conduct empirical studies in several text-based benchmarks, including the embodied environment ALFWorld (Shridhar et al., ), the interactive coding environment InterCode (Yang et al., ), and the standard planning benchmark BlocksWorld (Valmeekam et al., ). Across these three benchmarks, we measure the algorithm’s effectiveness by its success rate, which we define as the ratio of the number of task instances the algorithm successfully completes. More precisely, each task instance is defined by a target state $s_{g}\in\mathcal{S}$, and a task is deemed successfully completed if the algorithm reaches this target state $s_{H}=s_{g}$ at the end.

We will first delve into a detailed discussion of our implementation approach. Following this, we will present and analyze the results of our experiments.

### 4.1 Implementation Details

In our experiments, we introduce two primary simplifications to the $\mathtt{LINVIT}$ algorithm to enhance its efficiency and practicality. These modifications lead to a streamlined variant we denote as $\mathtt{SLINVIT}$, detailed in Algorithm 2. Below, we elaborate on each simplification.

Construction of Value Function and Exploration Policy. In Algorithm 1, we use a bonus in the construction of the value function and combine the uniform policy with the optimal policy in the regularized MDP in the exploration policy. This approach, while sample-efficient, introduces significant computational complexity. To optimize computation in our experiments, we simplify these processes.
Specifically, we directly combine the original value estimator $\widehat{V}$ with the log probability of the LLM policy $\mathbb{P}_{\text{LLM}}$, which is the key component in (3), to construct the value estimator in the experiment. Furthermore, we adopt a greedy policy with respect to this adjusted, regularized value estimator. This simplification enables a simplier computation by focusing on the core elements that drive the decision-making process.

Using Sub-Goals to Reduce Searching Complexity. Since the complexity of directly searching for the maximizor of the regularized value function is exponential in the horizon $H,$ we leverage sub-goal states to reduce the searching complexity. In the experiment, our algorithm works by decomposing the $H$-horizon planning problem into $H/N$(^1^11For notation convenience, we assume w.l.o.g. that $h$ can be divided by $N$.) sub-problems, each of which has a sub-goal and is of horizon $N$. More specifically, for each sub-problem $i\in[1,H/N]$, the corresponding sub-goal $s_{iN+1}$ is determined by solving

$$ $\displaystyle Q^{\mathrm{LLM}}(s_{(i-1)N},a_{(i-1)N+1:iN})$ $\displaystyle:=\widehat{V}(s_{iN+1})+\sum_{h=(i-1)N+1}^{iN}\lambda\pi_{h}^{ \mathrm{LLM}}(a_{h}|s_{h}),$ $\displaystyle a_{(i-1)N+1:iN}$ $\displaystyle:=\mathop{\mathrm{argmax}}_{a_{(i-1)N+1:iN}}Q^{\mathrm{LLM}}(s_{( i-1)N},a_{(i-1)N+1:iN}).$ (4.1) $$

where $\widehat{V}$ is the estimator of the true value $V^{\pi}$ and $\lambda\geq 0$ is a hyperparameter for the regularization. Compared with the regularized value function $\overline{V}$ in Section 3, we remove the logarithm term before $\mathbb{P}_{\mathrm{LLM}}$ for stability, such that it has a similar scale with $r\in[0,1]$. Here, $\widehat{V}$ can take various forms depending on both the true policy value it estimates and its own approximators, which we will discuss in more detail in Section 4.2.

Figure: Algorithm 2 Simplified Language-INtegrated Value Iteration ($\mathtt{SLINVIT}$)

Figure: Figure 2: Demonstration of the $\mathtt{SLINVIT}$ algorithm in the ALFWorld environment when $N=2$ and the tree breadth of BFS is set to $k=3$. The task is to “clean a cloth and put it on countertop”. The hallucination that LLM faces, i.e., the towel should be taken (instead of cloth), is addressed by the inherent exploration mechanism in our RL framework.
Refer to caption: x2.png

In practice, we implement a breadth-$k$ Breadth First Search (BFS) to approximate the actions in (4.1).
Specifically, the following procedure is repeated $N$ times: making $k$ copies of the agent that execute the top-$k$ outputs of the LLM by querying it “What is the potential next-step action?”. This will generate $k^{N}$ lookahead action sequences and the one with the highest $Q^{\mathrm{LLM}}$ is selected as $a_{(i-1)N+1:iN}$ and executed in the environment.

### 4.2 Instantiations of Value Estimator

In this section, we describe two instantiations of the value estimator $\widehat{V}$ in (4.1), named rule-based and Monte-Carlo value estimators. An illustration is provided in Figure 3.

Rule-Based Value Estimation. The rule-based value estimator is designed for scenarios where achieving the goal $s_{g}$ requires fulfilling multiple preconditions, such as in ALFWorld and BlocksWorld. It outputs the ratio of preconditions currently met by the state $s$. To achieve this, we prompt the LLM to estimate the value of the task by generating Python functions based on the task description ahead of evaluation. To avoid uncontrollable mistakes of the LLM, its response undergoes a one-time human review. This step is necessary only once because, although $s_{g}$ is changing during evaluation (e.g., put a cup on table and put a pen in drawer), the nature of the task and the structure of the preconditions (e.g., pick A and place A on B for any put task) do not vary.

Figure: (a) Rule-based value estimator.
Refer to caption: x3.png

For tasks where the goal’s preconditions are hard to determine, we propose the more general Monte-Carlo estimator.

Monte-Carlo Value Estimation. At the state $s_{h}$ to be evaluated, by sampling actions from the LLM policy $\pi^{\mathrm{LLM}}(\cdot\mid s_{h})$ until the planning horizon $H$ is reached, we obtain a partial trajectory. The Monte-Carlo value estimation is then given by averaging the cumulative reward received in $M$ such rollouts to approximate the value of the LLM policy, i.e.,

$$ $\displaystyle\widehat{V}=\frac{1}{M}\sum_{m=1}^{M/(H-h)}\sum_{n=h}^{H}r_{h}(s_ {n}^{m},a_{n}^{m}),$ $$

where $a_{n}^{m}\sim\pi^{\mathrm{LLM}}_{n}(\cdot\mid s_{n}^{m})$, and $s_{n+1}^{m}\sim P_{n}^{*}(\cdot\mid s_{n}^{m},a_{n}^{m})$.

### 4.3 ALFWorld

ALFWorld (Shridhar et al., ) is an interactive text-based environment with aligned embodied simulators. The benchmark encompasses $134$ virtual household task instances with predefined and fixed goals, each of which can be categorized into one of the six task types as shown in Table 1.

We provide a visualization of how $\mathtt{SLINVIT}$ works in the ALFWorld environment in Figure 2. Specifically, for each type of the six tasks, we use the rule-based value estimator to generate Python code that determines the preconditions of the task goal and the current state and outputs the portion of the satisfied preconditions as the estimated value. We set $N=2$ in our ALFWorld implementation.

**Table 1: Success rate (%) comparison of previous algorithms and $\mathtt{SLINVIT}$ in the ALFWorld environment.**
|  | Pick | Clean | Heat | Cool | Examine | PickTwo | Total |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\mathtt{BUTLER}$ | 46.00 | 39.00 | 74.00 | 100.00 | 22.00 | 24.00 | 37.00 |
| $\mathtt{ReAct}$ | 66.67 | 41.94 | 91.03 | 80.95 | 55.56 | 35.29 | 61.94 |
| $\mathtt{AdaPlanner}$ | 100.00 | 96.77 | 95.65 | 100.00 | 100.00 | 47.06 | 91.79 |
| $\mathtt{Reflexion}$ | 100.00 | 90.32 | 82.61 | 90.48 | 100.00 | 94.12 | 92.54 |
| $\mathtt{SLINVIT}$ | 100.00 | 100.00 | 91.30 | 90.48 | 100.00 | 100.00 | 97.01 |

Figure: Figure 4: Success rates with different numbers of samples.
Refer to caption: x5.png

We compare the success rate of $\mathtt{SLINVIT}$ and baselines in the ALFWorld environment in Table 1. We use GPT-3 (text-davinci-003) in our implementation.
For the baselines, $\mathtt{ReAct}$ (Yao et al., ), $\mathtt{AdaPlanner}$ (Sun et al., ), and $\mathtt{Reflexion}$ (Shinn et al., ) all use GPT-3 as their LLM agents, while $\mathtt{BUTLER}$ (Shridhar et al., ) is a RL-style imitation learning algorithm. Notably, the inferior performance of $\mathtt{BUTLER}$ indicates that RL algorithms may have difficulties understanding the task and generalize beyond. On the contrary, $\mathtt{SLINVIT}$ achieves the highest success rate in most categories of the task types and outperforms the baselines in terms of the overall success rate.

We also report the changes in success rate when the numbers of samples are different. The results are shown in Figure 4. The data points of $\mathtt{SLINVIT}$ are obtained by changing the tree breadth when performing BFS. Specifically, we set the tree breadth to $k=2,3,\cdots,10$ and report the overall success rate corresponding to different numbers of samples in all the $134$ tasks. For the $\mathtt{Reflexion}$ and $\mathtt{ReAct}$ baselines, the points in the plot are the results at the end of each trial. The sample number is calculated as the number of samples taken in the successful tasks in the current trial, plus all the samples in the previous trials. We observe that the proposed algorithm is able to achieve a higher success rate with fewer numbers of samples compared to methods that incorporate the environment feedback summary into the LLM as additional context.

### 4.4 InterCode

InterCode (Yang et al., ) is an interactive coding environment with code as actions and execution feedback as observations. It provides two benchmarks to evaluate the planning abilities of the large language models, namely InterCode-SQL and InterCode-Bash which use SQL and Bash commands as action spaces, respectively. For each benchmark, there are hundreds of tasks with predefined goals, such as find the name of airports which do not have any flight in and out and find all the text files in the testbed directory and subdirectories and concatenate them into a single file.

Unlike the ALFWorld environment where the task goals can be described by preconditions, there is no straightforward way to directly measure the value of the current state with explicit and simple rules in the InterCode environment. Therefore, we implement $\mathtt{SLINVIT}$ using the Monte-Carlo value estimator. Besides, we use the original dense reward as proposed in (Yang et al., ). We set the sub-problem horizon $N=1$ and the Monte-Carlo sampling number $M=1$.
For our method and all the baselines, we use GPT-3.5 (gpt-3.5-turbo).

The success rates in the InterCode-SQL and InterCode-Bash environments are reported in Table 2 and 3, respectively. The baselines we compare include $\mathtt{ReAct}$ (Yao et al., ), Plan & Solve (Wang et al., ), and Try Again (Yang et al., ), which is a vanilla LLM-based planning algorithm.
We observe that $\mathtt{SLINVIT}$ achieves the highest success rate in all the hardness modes of the InterCode-SQL benchmark, all the file systems of the InterCode-Bash benchmark, and has the best overall performance.

**Table 2: Success rate (%) comparison in the InterCode-SQL environment.**
|  | InterCode-SQL Hardness |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  | Easy | Medium | Hard | Extra | Total |
| $\mathtt{TryAgain}$ | 75.81 | 48.65 | 49.43 | 21.69 | 50.97 |
| $\mathtt{Plan}$ & Solve | 77.42 | 49.78 | 32.18 | 22.89 | 49.13 |
| $\mathtt{ReAct}$ | 80.24 | 65.47 | 47.13 | 20.48 | 58.70 |
| $\mathtt{SLINVIT}$ | 90.73 | 71.08 | 60.34 | 50.00 | 70.60 |

**Table 3: Success rate (%) comparison in the InterCode-Bash environment.**
|  | InterCode-Bash File System |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  | Sys 1 | Sys 2 | Sys 3 | Sys 4 | Total |
| $\mathtt{TryAgain}$ | 45.00 | 49.06 | 45.00 | 48.15 | 46.50 |
| $\mathtt{Plan\&Solve}$ | 0.00 | 45.28 | 43.33 | 22.22 | 28.00 |
| $\mathtt{ReAct}$ | 21.67 | 5.66 | 30.00 | 25.93 | 20.50 |
| $\mathtt{SLINVIT}$ | 55.00 | 60.38 | 64.41 | 66.67 | 60.80 |

In Table 4, we investigate the sample efficiency of the proposed algorithm in the InterCode environment. Specifically, we set the maximum number of samples in each episode to be $10$, $20$, and $30$ and report the corresponding success rates. For $\mathtt{SLINVIT}$, both the samples taken to maximize (4.1) and the samples for Monte-Carlo value estimation are counted. The results indicate that $\mathtt{SLINVIT}$ consistently outperforms the baselines with the same sample size and is thus more sample-efficient.

**Table 4: Success rate (%) under different maximum numbers of samples per episode.**
|  | SQL Sample Number | Bash Sample Number |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | 10 | 20 | 30 | 10 | 20 | 30 |
| $\mathtt{TryAgain}$ | 48.45 | 50.97 | 50.97 | 34.67 | 40.20 | 50.25 |
| $\mathtt{ReAct}$ | 52.61 | 52.71 | 53.67 | 20.50 | 21.10 | 21.61 |
| $\mathtt{SLINVIT}$ | 52.80 | 58.51 | 64.02 | 46.23 | 50.25 | 54.27 |

Ablation. We conduct an ablation study on the number of rollouts $M$ and the results are shown in Table 5. We observe that a more accurate value estimation corresponding to a larger $M$ leads to higher success rates for harder problems. Therefore, a trade-off can be taken between the sample number and the performance.

**Table 5: Ablation study on $\mathtt{SLINVIT}$ with different $M$.**
|  | InterCode-SQL Hardness |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  | Easy | Medium | Hard | Extra | Total |
| $M=1$ | 90.73 | 71.08 | 60.34 | 50.00 | 70.60 |
| $M=2$ | 88.31 | 77.13 | 65.52 | 52.42 | 73.89 |

### 4.5 BlocksWorld

BlocksWorld (Valmeekam et al., ; Liu et al., ) is another planning benchmark that contains various tasks to arrange blocks in specific configurations. The state is the current configuration of the blocks and the action is an instruction that moves blocks. Specifically, an action is composed of one of the four verbs (Stack, Unstack, Put, and Pickup) and the operated block. Similar to the implementation in ALFWorld, we also adopt the rule-based value estimator. Specifically, the goal state of each task is defined as the combination of several block arrangements (e.g., block 1 is on top of block 2). With the current state as input, the value estimator then returns the proportion of the satisfied arrangements.

Following $\mathtt{RAP}$ Hao et al. (), we group the task instances in Valmeekam et al. () by the minimum number of actions required, leading to $57$ cases solvable within $4$ steps, and $114$ cases within $6$ steps. We evaluate our method and the $\mathtt{RAP}$ baseline by comparing the success rates under different numbers of samples. We evaluate the Vicuna-13b(v1.3) and the results are shown in Figure 5. Our method consistently outperforms $\mathtt{RAP}$ and achieves a higher success rate with fewer samples.

Figure: (a) 4-step
Refer to caption: x6.png

## 5 Theory

In this section, we present the analysis of $\mathtt{LINVIT}$. To begin, we define the KL divergence between two policies.

###### Definition 5.1 (KL-divergence between two policy) .

For two policies $\pi_{1}=\{\pi_{1}^{h}\}_{h=1}^{H}$ and $\pi_{2}=\{\pi_{2}^{h}\}_{h=1}^{H}$, we define

$$ $\displaystyle{\mathrm{KL}}(\pi^{1}\|\pi^{2})=\sum_{h=1}^{H}\mathbb{E}_{\pi^{1} }\Bigl{[}{\mathrm{KL}}\bigl{(}\pi_{h}^{1}(\cdot|s_{h})\|\pi_{h}^{2}(\cdot|s_{h })\bigr{)}\Bigr{]}.$ $$

Definition 5.1 provides a quantitative measure of the similarity between two policies. More specifically, the divergence is small when two policies are similar. Building on this foundational understanding, we present the following theorem.

###### Theorem 5.2 .

We assume that ${\mathrm{KL}}(\pi^{*}\|\pi^{\mathrm{LLM}})\leq\epsilon_{\mathrm{LLM}}$, and set the tuning parameter

$$ $\displaystyle\lambda=\epsilon/(2\epsilon_{\mathrm{LLM}}),\;\;T=CH^{6}SA^{4} \log^{2}(HSA/\delta)/\epsilon^{2}$ $$

for some absolute constant $C$. We then have $V_{1}^{*}(s_{1})-V_{1}^{\widehat{\pi}}(s_{1})\leq\epsilon$ with probability as least $1-\delta$.

###### Proof.

See Appendix §A for a detailed proof.
∎

Theorem 5.2 demonstrates that the number of samples required to achieve $\epsilon$-optimality is proportional to the KL divergence, ${\mathrm{KL}}(\pi^{*}\|\pi^{\mathrm{LLM}})$, given that $\lambda$ is suitably chosen. This relationship implies a reduced sample necessity when $\pi^{\mathrm{LLM}}$ closely aligns with the optimal policy $\pi^{*}$. The intuitive rationale behind this is that the demand for exploration diminishes when an initial policy is nearly optimal. Consequently, this theorem underscores the efficacy of our algorithm in capitalizing on the policy information provided by the Large Language Model (LLM), thereby validating its practical utility in decision-making scenarios. Theorem 5.2 further demonstrates that Algorithm 1 is capable of achieving $\epsilon$-optimality, even in cases where $\epsilon\leq\epsilon_{\mathrm{LLM}}$, contingent upon the collection of a sufficient number of samples. This finding underscores the algorithm’s robustness in attaining a specified level of optimality.

In Theorem 5.2, the regularization coefficient $\lambda$ became bigger as the KL divergence become smaller. This trend aligns intuitively with the principle of relying more heavily on the information provided by the Large Language Model (LLM) when there is evidence that the policy it offers is effective. Essentially, a smaller KL divergence indicates a closer alignment between the LLM’s policy and the optimal policy, justifying increased reliance on the LLM’s guidance in these scenarios.

###### Definition 5.1 (KL-divergence between two policy) .

###### Theorem 5.2 .

###### Proof.

## 6 Related Work

Reinforcement Learning with Language. Language offers a particularly effective medium for tackling decision-making challenges due to its succinct and structured format. This quality has made it a valuable tool for numerous reinforcement learning (RL) algorithms (Sutton et al., ; Mnih et al., ; Zhang, ; Zhang et al., ), enabling them to learn from high-level specifications of goals (Jiang et al., ; Lynch and Sermanet, ; Hejna et al., ) or to benefit from the step-by-step instructions provided by large language models (LLMs) (Ahn et al., ; Huang et al., ). Additionally, research has ventured into harnessing more expansive language applications to model the dynamics and reward mechanisms of environments, employing planning algorithms to guide decision-making processes (Bialystok, ; Liu et al., ). Different from these approaches, our work introduces the novel concept of applying LLMs as regularizing agents within value-based RL frameworks.

Decision-Making with Language Models. The strong capabilities language models exhibit have opened a new avenue for LLM agents to interact with the real world autonomously for decision-making tasks. Inspired by classical planning literature (Bonet and Geffner, ; Hoffmann and Nebel, ; Chitnis et al., ; Gehring et al., ) that uses heuristic functions as dense reward generators to perform informed search, recent works (Lin et al., ; Hao et al., ) proposed to use the LLM as the heuristic function. The remarkable programming abilities exhibited by the LLM have also enabled converting natural language instructions into planning languages and then adopting the classical planner (Liu et al., ; Liang et al., ; Silver et al., ; Xie et al., ), which, however, are constrained in narrowed domains and predefined environments. Moreover, a recent line of work (Yao et al., , ; Liu et al., ; Sel et al., ; Zhang et al., ) has developed various prompting schemes to enhance LLM reasoning, though these approaches generally do not integrate feedback from the environment into the decision-making process.

A large body of previous works focused on prompt engineering by providing the LLM with additional contextual information and templates to complete the task. Among them, the $\mathtt{ReAct}$ (Yao et al., ) agent generates both reasoning traces and task-specific actions in an interleaved manner, Plan-and-Solve (Wang et al., ) improves the Chain-of-Thought (Wei et al., ) prompt to devise a fixed high-level plan before taking actions in the environment, and Huang et al. () prompt the LLM to extract temporally extended plans in a zero-shot manner. Besides, other works directly train the model on embodied decision-making data (Suglia et al., ; Sharma et al., ; Mezghani et al., ; Driess et al., ) or multi-modal data (Lu et al., ; Li et al., ; Radford et al., ; Zellers et al., ) by learning additional downstream networks on top of the pre-trained LLM (Lynch and Sermanet, ; Akakzia et al., ; Zellers et al., ) or finetuning in the environment (Reid et al., ; Li et al., ; Chen et al., ). Similar to our work, Ahn et al. (); Hu and Sadigh (); Lin et al. (); Hao et al. () also use value functions to ground the LLM agent, but the sub-problem horizon is set to $1$ and the executed actions are one-step greedy without backtracking, which still suffers from the curse of the long horizon. Works building on the self-reflection abilities of LLMs (Shinn et al., ; Sun et al., ; Ma et al., ) also demonstrate limitations in refining initial strategies based on feedback, as shown in our experiments.

## 7 Conclusion

Large language models (LLMs) have shown remarkable capabilities in quickly generating viable initial strategies for decision-making tasks, even with minimal or no prior examples. However, these LLM-driven agents struggle to iteratively refine their strategies based on feedback from their environment, mainly because they lack the ability to effectively explore and reason from the feedback. In contrast, reinforcement learning (RL) excels at adapting and improving through feedback, though it often requires an extensive amount of trial-and-error to gather improvable feedback, hindered by its inability to leverage common sense reasoning. To improve the sample efficiency of RL algorithms, in this work, we propose a novel RL framework with LLM as a policy prior. We prove that the number of samples required by our algorithm is proportional to the KL divergence between the LLM and the optimal policy. This result is further evidenced through experiments in interactive environments such as ALFWorld, InterCode, and BlocksWorld, underscoring our method’s improved sample efficiency.

## Appendix A Proof of Theorem 5.2

###### Proof.

To analyze the property of $\mathtt{LINVIT}$, we introduce the definition of the prior-regularized value function. The prior-regularized value function $Q_{\mathrm{LLM},\lambda,h}^{\pi}$, $V_{\mathrm{LLM},\lambda,h}^{\pi}(s_{h})$ and $V_{\mathrm{LLM},\lambda,h}^{*}$ are defined as

$$ $\displaystyle Q_{\mathrm{LLM},\lambda,h}^{\pi}(s_{h},a_{h})$ $\displaystyle=r_{h}(s_{h},a_{h})+\mathbb{E}_{s_{h+1\sim P_{h}}}\bigl{[}V_{ \mathrm{LLM},\lambda,h+1}^{\pi}(s_{h+1})\bigr{]},$ $\displaystyle V_{\mathrm{LLM},\lambda,h}^{\pi}(s_{h})$ $\displaystyle=\mathbb{E}_{a_{h}\sim\pi_{h}(\cdot|s_{h})}Q_{\mathrm{LLM}, \lambda,h}^{\pi}(s_{h},a_{h})-\lambda\mathrm{KL}\bigl{(}\pi_{h}(\cdot|s_{h})\| \pi^{\mathrm{LLM}}_{h}(\cdot|s_{h})\bigr{)}.$ $\displaystyle V_{\mathrm{LLM},\lambda,h}^{*}(s_{h})$ $\displaystyle=\max_{\pi}V_{\mathrm{LLM},\lambda,h}^{\pi}(s_{h}).$ $$

$\mathtt{LINVIT}$ can be viewed as an algorithm that maximizes the prior-regularized value function by interacting with the environment. The prior-regularized value function can be viewed as a regularized version of the original value functions that favors the policies that similar with $\pi^{\mathrm{LLM}}$. The following lemma connects the KL-regularized value with the original value.

###### Lemma A.1 .

When ${\mathrm{KL}}(\pi^{*}\|\pi^{\mathrm{LLM}})\leq\epsilon_{\mathrm{LLM}}$, we have

$$ $\displaystyle V_{1}^{*}(s_{1})-V_{1}^{\widehat{\pi}}(s_{1})\leq V^{\star}_{ \mathrm{LLM},\lambda,h}(s_{1})-V^{\widehat{\pi}}_{\mathrm{LLM},\lambda,h}(s_{1 })+\lambda\epsilon_{\mathrm{LLM}}.$ $$

Here ${\mathrm{KL}}(\pi^{1}\|\pi^{2})=\sum_{h=1}^{H}\mathbb{E}_{\pi^{1}}[{\mathrm{KL
}}(\pi_{h}^{1}(\cdot|s_{h})\|\pi_{h}^{2}(\cdot|s_{h}))]$.

###### Proof.

See §B.1 for a detailed proof.
∎

The following lemma show that, our algorithm provably find the optimal policy with respect to the prior-regularized value function with high probability.

###### Lemma A.2 .

With probability $1-\delta$, we have

$$ $\displaystyle V^{\star}_{\mathrm{LLM},\lambda,h}(s_{1})-V^{\widehat{\pi}}_{ \mathrm{LLM},\lambda,h}(s_{1})\leq\epsilon/2.$ $$

###### Proof.

See §B.2 for a detailed proof.
∎

We denote by $\mathcal{E}_{1}$ the event in Lemma A.2. We then have $P(\mathcal{E}_{1})\geq 1-\delta$. Since we set $\lambda=\epsilon/(\epsilon_{\mathrm{LLM}})$, we have

$$ $\displaystyle V_{1}^{*}(s_{1})-V_{1}^{\widehat{\pi}}(s_{1})\leq V^{\star}_{ \mathrm{LLM},\lambda,h}(s_{1})-V^{\widehat{\pi}}_{\mathrm{LLM},\lambda,h}(s_{1 })+\epsilon/2\leq\epsilon$ $$

by Lemma A.1 when we condition on Event $\mathcal{E}_{1}$. Therefore, we conclude the proof of Theorem 5.2.

∎

###### Proof.

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

## Appendix B Proof of Auxiliary Lemmas

### B.1 Proof of Lemma A.1

###### Proof.

By the definitions of $V^{\pi^{*}}_{\pi^{\mathrm{LLM}},\lambda,h}$ and $V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})$, we have

$$ $\displaystyle V_{1}^{*}(s_{1})$ $\displaystyle=V^{\pi^{*}}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})+\lambda{ \mathrm{KL}}(\pi^{*},\pi^{\mathrm{LLM}})$ $\displaystyle=V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})+\lambda{\mathrm{ KL}}(\pi^{*},\pi^{\mathrm{LLM}}).$ $$

Therefore, when ${\mathrm{KL}}(\pi^{*},\pi^{\mathrm{LLM}})\leq\epsilon_{\mathrm{LLM}}$, we have

$$ $\displaystyle V_{1}^{*}(s_{1})-V_{1}^{\widehat{\pi}}(s_{1})$ $\displaystyle\leq V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})-V^{\widehat{ \pi}}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})+\lambda{\mathrm{KL}}(\pi^{*},\pi^{ \mathrm{LLM}})$ $\displaystyle\leq V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})-V^{\widehat{ \pi}}_{\pi^{\mathrm{LLM}},\lambda,h}(s_{1})+\lambda\epsilon_{\mathrm{LLM}},$ $$

which concludes the proof of Lemma A.1.
∎

###### Proof.

### B.2 Proof of Lemma A.2

###### Proof.

The proof of Lemma A.2 consists of two parts. We decompose the regret in the first part, and upper bound the decomposed regret in the second part.

By the definition of $\widehat{\pi}$ in Algorithm $\mathtt{LINVIT}$, we have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,1}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,1}(s)=\frac{1}{T}\sum_{t=1}^{T}\bigl{[}V^{ \star}_{\pi^{\mathrm{LLM}},\lambda,1}(s)-V^{\overline{\pi}^{t+1}}_{\pi^{ \mathrm{LLM}},\lambda,1}(s)\bigr{]}.$ (B.1) $$

We also have the following lemma.

###### Lemma B.1 .

We have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,1}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,1}(s)\leq\frac{A}{2\lambda}\sum_{h=1}^{H} \mathbb{E}_{\bar{\pi}^{t+1}}\Bigl{[}\max_{a\in\mathcal{A}}\bigl{(}\overline{Q} _{h}^{t}(s_{h},a)-\underline{Q}_{h}^{t}(s_{h},a)\bigr{)}^{2}\Bigr{]}$ $$

holds for all $(t,s)\in[T]\times{\mathcal{S}}$ with probability $1-\delta/2$.

###### Proof.

See §B.4 for a detailed proof.
∎

Therefore, we have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,1}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,1}(s)\leq\frac{A}{2T\lambda}\sum_{t=1}^{T} \sum_{h=1}^{H}\mathbb{E}_{\bar{\pi}^{t+1}}\Bigl{[}\max_{a\in\mathcal{A}}\bigl{ (}\overline{Q}_{h}^{t}(s_{h},a)-\underline{Q}_{h}^{t}(s_{h},a)\bigr{)}^{2} \Bigr{]}$ (B.2) $$

The following lemma upper bounds the decomposed regret.

###### Lemma B.2 .

We have

$$ $\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\overline{\pi}^{t+1}} \left[\max_{a\in\mathcal{A}}\left(\overline{Q}^{t}_{h}(s_{h},a)-\underline{Q}^ {t}_{h}(s_{h},a)\right)^{2}\right]\leq 920SA^{3}H^{6}\log^{2}(12HTS^{2}A/\delta)$ $$

holds with probability at least $1-\delta/4$.

###### Proof.

See §B.5 for a detailed proof.
∎

Therefore, we have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,1}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,1}(s)\leq 460SA^{4}H^{6}\log^{2}(12HTS^{2}A/ \delta)/(T\lambda)$ (B.3) $$

when the event in Lemmas B.1 and B.2 hold. Therefore, when $\lambda=\epsilon/(2\epsilon_{\mathrm{LLM}})$ and $T=CSA^{4}H^{6}\log^{2}(HTSA/\delta)/\epsilon^{2}$ for some absolute constant $c$, we have $V^{\star}_{\pi^{\mathrm{LLM}},\lambda,1}(s)-V^{\overline{\pi}^{t+1}}_{\pi^{
\mathrm{LLM}},\lambda,1}(s)\leq\epsilon$, which concludes the proof of Lemma A.1.
∎

###### Proof.

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

### B.3 Proof of Lemma B.6

###### Proof.

First, we have the following lemma, which shows that the bonus we define characterizes the uncertainty of the model estimation with high probability.

###### Lemma B.3 .

We have

$$ $\displaystyle\mathbbm{1}_{n_{h}^{t}(s,a)>0}\mathop{\mathrm{TV}}\bigl{(}P_{h}^{ *}(\cdot\mid s,a),P_{h}^{t}(\cdot\mid s,a)\bigr{)}\leq A\sqrt{\frac{\log(4HTS^ {2}A/\delta)}{n_{h}^{t}(s,a)}}$ $$

holds for all $(t,h,s,a)\in[T]\times[H]\times{\mathcal{S}}\times\mathcal{A}$ with probability at least $1-\delta/2$.

###### Proof.

See §B.6 for a detailed proof.
∎

We denote by $\mathcal{E}_{3}$ the event in Lemma B.3. In the following part of the proof, we condition on Event $\mathcal{E}_{3}$. We prove Lemma B.6 using induction on $h$. By the definition of $\overline{Q}^{t}_{H+1}$ and $Q^{\star}_{\mathrm{LLM},\lambda,H+1}(s,a)$, Lemma B.6 holds when $h=H+1$. We also have the following lemma, which shows that the prior-regularized value function is bounded.

###### Lemma B.4 (Boundedness of $Q^{\star}_{\mathrm{LLM},\lambda,h}$ ) .

We have

$$ $\displaystyle 0\leq Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)\leq H+1-h;\quad \quad 0\leq V^{\star}_{\mathrm{LLM},\lambda,h}(s)\leq H+1-h$ $$

holds for all $(s,a,h)\in{\mathcal{S}}\times\mathcal{A}\times[H+1]$.

###### Proof.

See §B.7 for a detailed proof.
∎

By Lemma B.4, Lemma B.6 obviously holds when $\overline{Q}^{t}_{h}\geq H$. Otherwise, we have

$$ $\displaystyle\overline{Q}^{t}_{h}(s,a)-Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)$ $\displaystyle=\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}^{t}(s^{\prime}\mid s,a) \overline{V}^{t}_{h+1}(s^{\prime})-\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}^{*}( s^{\prime}\mid s,a)V^{\star}_{\mathrm{LLM},\lambda,h+1}(s^{\prime})+u^{t}_{h}( s,a)$ $\displaystyle\geq\sum_{s^{\prime}\in{\mathcal{S}}}\bigl{[}P_{h}^{t}(s^{\prime} \mid s,a)-P_{h}^{*}(s^{\prime}\mid s,a)\bigr{]}V^{\star}_{\mathrm{LLM},\lambda ,h+1}(s^{\prime})+u^{t}_{h}(s,a)$ $$

when the induction hypothesis holds. Since $|V^{\star}_{\mathrm{LLM},\lambda,h+1}(s^{\prime})|\leq H$, we have

$$ $\displaystyle\overline{Q}^{t}_{h}(s,a)-Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)$ $\displaystyle\geq u^{t}_{h}(s,a)-H\sum_{s^{\prime}\in{\mathcal{S}}}\bigl{|}P_{ h}^{t}(s^{\prime}\mid s,a)-P_{h}^{*}(s^{\prime}\mid s,a)\bigr{|}$ $\displaystyle=u^{t}_{h}(s,a)-H\mathop{\mathrm{TV}}(P_{h}^{t}(\cdot\mid s,a),P_ {h}^{*}(\cdot\mid s,a)).$ $$

When we condition on $\mathcal{E}_{3}$, we have

$$ $\displaystyle H\mathop{\mathrm{TV}}(P_{h}^{t}(\cdot\mid s,a),P_{h}^{*}(\cdot \mid s,a))\leq\max\biggl{\{}2H,\sqrt{\frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s ,a)}}\biggr{\}}=u^{t}_{h}(s,a),$ (B.4) $$

which implies $\overline{Q}^{t}_{h}(s,a)\geq Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)$. Therefore, we have

$$ $\displaystyle\overline{V}^{t}_{h}(s)$ $\displaystyle=\max_{\pi(\cdot\mid s)}\sum_{a\in\mathcal{A}}\pi(a\mid s) \overline{Q}^{t}_{h}(s,a)-\lambda{\mathrm{KL}}\bigl{(}\pi(\cdot\mid s),\pi^{ \mathrm{LLM}}(\cdot\mid s)\bigr{)}$ $\displaystyle\geq\max_{\pi(\cdot\mid s)}\sum_{a\in\mathcal{A}}\pi(a\mid s)Q^{ \star}_{\mathrm{LLM},\lambda,h}(s,a)-\lambda{\mathrm{KL}}\bigl{(}\pi(\cdot\mid s ),\pi^{\mathrm{LLM}}(\cdot\mid s)\bigr{)}=V^{\star}_{\mathrm{LLM},\lambda,h}(s),$ $$

which concludes the first part of the proof.

By the definition of $\underline{Q}^{t}_{H+1}$ and $Q^{\star}_{\mathrm{LLM},\lambda,H+1}(s,a)$, Lemma B.6 holds when $h=H+1$. By the boundedness of $Q^{\star}_{\mathrm{LLM},\lambda,h}$, Lemma B.6 obviously holds when $\underline{Q}^{t}_{h}\leq 0$. Otherwise, we have

$$ $\displaystyle\underline{Q}^{t}_{h}(s,a)-Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)$ $\displaystyle\leq\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}^{t}(s^{\prime}\mid s,a )\underline{V}^{t}_{h+1}(s^{\prime})-\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}^{* }(s^{\prime}\mid s,a)V^{\star}_{\mathrm{LLM},\lambda,h+1}(s^{\prime})-u^{t}_{h }(s,a)$ $\displaystyle\leq\sum_{s^{\prime}\in{\mathcal{S}}}\bigl{[}P_{h}^{t}(s^{\prime} \mid s,a)-P_{h}^{*}(s^{\prime}\mid s,a)\bigr{]}V^{\star}_{\mathrm{LLM},\lambda ,h+1}(s^{\prime})-u^{t}_{h}(s,a)$ $$

when the induction hypothesis holds. Since $|V^{\star}_{\mathrm{LLM},\lambda,h+1}(s^{\prime})|\leq H$, we have

$$ $\displaystyle\underline{Q}^{t}_{h}(s,a)-Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)$ $\displaystyle\geq H\sum_{s^{\prime}\in{\mathcal{S}}}\bigl{|}P_{h}^{t}(s^{ \prime}\mid s,a)-P_{h}^{*}(s^{\prime}\mid s,a)\bigr{|}-u^{t}_{h}(s,a)$ $\displaystyle=H\mathop{\mathrm{TV}}(P_{h}^{t}(\cdot\mid s,a),P_{h}^{*}(\cdot \mid s,a))-u^{t}_{h}(s,a).$ $$

Therefore, we have $\underline{Q}^{t}_{h}(s,a)\geq Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)$ when we condition on $\mathcal{E}_{3}$ by (B.4). We have

$$ $\displaystyle\underline{V}^{t}_{h}(s)$ $\displaystyle=\max_{\pi(\cdot\mid s)}\sum_{a\in\mathcal{A}}\pi(a\mid s) \underline{Q}^{t}_{h}(s,a)-\lambda{\mathrm{KL}}\bigl{(}\pi(\cdot\mid s),\pi^{ \mathrm{LLM}}(\cdot\mid s)\bigr{)}$ $\displaystyle\geq\max_{\pi(\cdot\mid s)}\sum_{a\in\mathcal{A}}\pi(a\mid s)Q^{ \star}_{\mathrm{LLM},\lambda,h}(s,a)-\lambda{\mathrm{KL}}\bigl{(}\pi(\cdot\mid s ),\pi^{\mathrm{LLM}}(\cdot\mid s)\bigr{)}=V^{\star}_{\mathrm{LLM},\lambda,h}(s),$ $$

which conclude the proof of Lemma B.6.
∎

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Lemma B.4 (Boundedness of Q LLM , λ , h ⋆ subscript superscript 𝑄 ⋆ LLM 𝜆 ℎ Q^{\star}_{\mathrm{LLM},\lambda,h} italic_Q start_POSTSUPERSCRIPT ⋆ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT roman_LLM , italic_λ , italic_h end_POSTSUBSCRIPT ) .

###### Proof.

### B.4 Proof of Lemma B.1

###### Proof.

We have the following lemma.

###### Lemma B.5 .

For two vectors $x=(x_{1},\ldots,x_{A})\in{}^{A}$ and $\bar{x}=(\bar{x}_{1},\ldots,\bar{x}_{A})\in{}^{A}$, we have

$$ $\displaystyle\max_{\sum_{i=1}^{A}\beta_{i}=1,\beta_{i}>0}\Bigl{[}\sum_{i=1}^{A }x_{i}\beta_{i}-\lambda\sum_{i=1}^{A}\beta_{i}\log\frac{\beta_{i}}{\widetilde{ \beta}_{i}}\Bigr{]}-\max_{\sum_{i=1}^{A}\beta_{i}=1,\beta_{i}>0}\Bigl{[}\sum_{ i=1}^{A}\bar{x}_{i}\beta_{i}-\lambda\sum_{i=1}^{A}\beta_{i}\log\frac{\beta_{i} }{\widetilde{\beta}_{i}}\Bigr{]}$ $\displaystyle\qquad\qquad\leq\sum_{i=1}^{A}\bar{\beta}_{i}(x_{i}-\bar{x}_{i})+ \frac{A}{2\lambda}\max_{i}|x_{i}-\bar{x}_{i}|^{2},$ $$

where $\{\bar{\beta}_{i}\}=\mathop{\mathrm{argmax}}_{\sum_{i=1}^{A}\beta_{i}=1,\beta_
{i}>0}\Bigl{[}\sum_{i=1}^{A}\bar{x}_{i}\beta_{i}-\sum_{i=1}^{A}\beta_{i}\log
\frac{\beta_{i}}{\widetilde{\beta}_{i}}\Bigr{]}$.

###### Proof.

See §B.8 for a detailed proof.
∎

We prove Lemma B.1 using induction on $h$. The statement obviously holds when $h=H+1$.

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,h}(s)=V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h }(s)-\overline{V}^{t}_{h}(s)+\overline{V}^{t}_{h}(s)-V^{\overline{\pi}^{t+1}}_ {\pi^{\mathrm{LLM}},\lambda,h}(s).$ (B.5) $$

By the definition of $V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}$, $V^{\overline{\pi}^{t+1}}_{\pi^{\mathrm{LLM}},\lambda,h}$ and Lemma B.5, we have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s)-\overline{V}^{t}_{h} (s)$ (B.6) $\displaystyle\quad\quad\leq\sum_{a\in\mathcal{A}}\bar{\pi}_{h}^{t+1}(a\mid s) \bigl{[}Q^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s,a)-\overline{Q}^{t}_{h}(s,a )\bigr{]}+\frac{A}{2\lambda}\max_{a}|Q^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}( s,a)-\overline{Q}^{t}_{h}(s,a)|^{2}.$ $$

We also have

$$ $\displaystyle\overline{V}^{t}_{h}(s)-V^{\overline{\pi}^{t+1}}_{\pi^{\mathrm{ LLM}},\lambda,h}(s)=\sum_{a\in\mathcal{A}}\bar{\pi}_{h}^{t+1}(a\mid s)\bigl{[} \overline{Q}^{t}_{h}(s,a)-Q^{\overline{\pi}^{t+1}}_{\pi^{\mathrm{LLM}},\lambda ,h}(s,a)\bigr{]}.$ (B.7) $$

Combining (B.5), (B.6) and (B.7), we have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,h}(s)$ $\displaystyle\quad\quad\leq\sum_{a\in\mathcal{A}}\bar{\pi}_{h}^{t+1}(a\mid s) \bigl{[}Q^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s,a)-Q^{\overline{\pi}^{t+1}} _{\pi^{\mathrm{LLM}},\lambda,h}(s,a)\bigr{]}+\frac{A}{2\lambda}\max_{a}|Q^{ \star}_{\pi^{\mathrm{LLM}},\lambda,h}(s,a)-\overline{Q}^{t}_{h}(s,a)|^{2}$ $\displaystyle\quad\quad=\mathbb{E}_{\bar{\pi}^{t+1}}\bigl{[}V^{\star}_{\pi^{ \mathrm{LLM}},\lambda,h+1}(s_{h+1},a_{h+1})-V^{\overline{\pi}^{t+1}}_{\pi^{ \mathrm{LLM}},\lambda,h+1}(s_{h+1},a_{h+1})\mid s_{h}=s\bigr{]}+\frac{A}{2 \lambda}\max_{a}|Q^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s,a)-\overline{Q}^{t }_{h}(s,a)|^{2}$ $$

By induction, we easily have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,h}(s)\leq\frac{A}{2\lambda}\sum_{h^{\prime}=h }^{H}\mathbb{E}_{\bar{\pi}^{t+1}}\Bigl{[}\max_{a}|Q^{\star}_{\pi^{\mathrm{LLM} },\lambda,h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})-\overline{Q}^{t}_{h^{ \prime}}(s_{h^{\prime}},a_{h^{\prime}})|^{2}\;\big{|}\;s_{h}=s\Bigr{]}.$ (B.8) $$

We also have the following lemma, which shows that $Q^{\star}_{\pi^{\mathrm{LLM}},\lambda,h^{\prime}}$ lies between $\overline{Q}^{t}_{h^{\prime}}$ and $\underline{Q}^{t}_{h^{\prime}}$.

###### Lemma B.6 .

We have

$$ $\displaystyle\underline{Q}^{t}_{h}(s,a)\leq Q^{\star}_{\pi^{\mathrm{LLM}}, \lambda,h}(s,a)\leq\overline{Q}^{t}_{h}(s,a),\qquad\underline{V}^{t}_{\lambda, h}(s)\leq V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s)\leq\overline{V}^{t}_{h}(s)$ $$

holds for all $t\in\mathbb{N}$, $(h,s,a)\in[H]\times{\mathcal{S}}\times\mathcal{A}$ with probability $1-\delta/2$.

###### Proof.

See §B.3 for a detailed proof.
∎

Therefore, by (B.8), we have

$$ $\displaystyle V^{\star}_{\pi^{\mathrm{LLM}},\lambda,h}(s)-V^{\overline{\pi}^{t +1}}_{\pi^{\mathrm{LLM}},\lambda,h}(s)\leq\frac{A}{2\lambda}\sum_{h^{\prime}=h }^{H}\mathbb{E}_{\bar{\pi}^{t+1}}\Bigl{[}\max_{a}|\overline{Q}^{t}_{h^{\prime} }(s_{h^{\prime}},a_{h^{\prime}})-\underline{Q}^{t}_{h^{\prime}}(s_{h^{\prime}} ,a_{h^{\prime}})|^{2}\;\big{|}\;s_{h}=s\Bigr{]}$ (B.9) $$

when the event in Lemma B.6 holds, which conclude the proof of Lemma B.1.

∎

###### Proof.

###### Lemma B.5 .

###### Proof.

###### Lemma B.6 .

###### Proof.

### B.5 Proof of Lemma B.2

###### Proof.

By the definition of $\pi^{t}$ in (3.4), we have

$$ $\displaystyle\mathbb{E}_{\overline{\pi}^{t+1}}\left[\max_{a\in\mathcal{A}} \left(\overline{Q}^{t}_{h}(s_{h},a)-\underline{Q}^{t}_{h}(s_{h},a)\right)^{2}\right]$ $\displaystyle\leq H\Bigl{(}\frac{H}{H-1}\Bigr{)}^{h-1}\mathbb{E}_{\pi^{t+1}} \left[\left(\overline{Q}^{t}_{h}(s_{h},a_{h})-\underline{Q}^{t}_{h}(s_{h},a_{h })\right)^{2}\right]$ (B.10) $\displaystyle\leq eH\mathbb{E}_{\pi^{t+1}}\left[\left(\overline{Q}^{t}_{h}(s_{ h},a_{h})-\underline{Q}^{t}_{h}(s_{h},a_{h})\right)^{2}\right].$ $$

Next we analyze the expression under the square. First, we have

$$ $\displaystyle\overline{Q}^{t}_{h}(s_{h},a_{h})-\underline{Q}^{t}_{h}(s_{h},a_{ h})$ $\displaystyle\leq 2u_{h}^{t}(s_{h},a_{h})+\sum_{a\in\mathcal{A}}P_{h}^{t}(s^{ \prime}|s_{h},a_{h})[\overline{V}^{t}_{h+1}(s^{\prime})-\underline{V}^{t}_{h+1 }(s^{\prime})]$ $\displaystyle\leq 2u_{h}^{t}(s_{h},a_{h})+\sum_{a\in\mathcal{A}}P_{h}^{*}(s^{ \prime}|s_{h},a_{h})[\overline{V}^{t}_{h+1}(s^{\prime})-\underline{V}^{t}_{h+1 }(s^{\prime})]+H\mathop{\mathrm{TV}}(P_{h}^{t}(\cdot\mid s,a),P_{h}^{*}(\cdot \mid s,a)).$ $$

Therefore, by (B.4), we have

$$ $\displaystyle\overline{Q}^{t}_{h}(s_{h},a_{h})-\underline{Q}^{t}_{h}(s_{h},a_{ h})\leq 3u_{h}^{t}(s_{h},a_{h})+\sum_{a\in\mathcal{A}}P_{h}^{*}(s^{\prime}|s_{ h},a_{h})[\overline{V}^{t}_{h+1}(s^{\prime})-\underline{V}^{t}_{h+1}(s^{\prime })].$ $$

Therefore, we have

$$ $\displaystyle\overline{Q}^{t}_{h}(s_{h},a_{h})-\underline{Q}^{t}_{h}(s_{h},a_{ h})$ $\displaystyle\leq 3AH\cdot\mathbb{E}_{\overline{\pi}^{t+1}}\Biggl{[}\sum_{h^{ \prime}=h}^{H}\sqrt{\frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a)}}\bigg{|}s_{h }\Biggl{]}$ $\displaystyle\leq 9AH\cdot\mathbb{E}_{\pi^{t+1}}\Biggl{[}\sum_{h^{\prime}=h}^{ H}\sqrt{\frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a)}}\bigg{|}s_{h}\Biggl{]}$ $$

by induction and the definition of $u_{h}^{t}$ in (3.1). By Cauchy inequality, we have

$$ $\displaystyle\overline{Q}^{t}_{h}(s_{h},a_{h})-\underline{Q}^{t}_{h}(s_{h},a_{ h})\leq 9AH^{3/2}\sqrt{\mathbb{E}_{\pi^{t+1}}\Biggl{[}\sum_{h^{\prime}=h}^{H} \frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a)}\bigg{|}s_{h}\Biggl{]}}.$ (B.11) $$

Combining (B.10) and (B.11), we have

$$ $\displaystyle\mathbb{E}_{\overline{\pi}^{t+1}}\left[\max_{a\in\mathcal{A}} \left(\overline{Q}^{t}_{h}(s_{h},a)-\underline{Q}^{t}_{h}(s_{h},a)\right)^{2}\right]$ $\displaystyle\leq 230A^{2}H^{4}\mathbb{E}_{\pi^{t+1}}\left[\mathbb{E}_{\pi^{t+ 1}}\Biggl{[}\sum_{h^{\prime}=h}^{H}\frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a )}\bigg{|}s_{h}\Biggl{]}\right]$ (B.12) $\displaystyle=230A^{2}H^{4}\mathbb{E}_{\pi^{t+1}}\left[\sum_{h^{\prime}=h}^{H} \frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a)}\bigg{|}s_{h}\right].$ $$

We also have the following lemma.

###### Lemma B.7 .

We define

$$ $\displaystyle\mathcal{E}^{\mathrm{cnt}}\triangleq\{n_{h}^{t}(s,a)\geq\frac{1}{ 2}\bar{n}_{h}^{t}(s,a)-\log(12SAH/\delta)\text{ for all }(s,a,h,t)\in{\mathcal {S}}\times\mathcal{A}\times[H]\times[T]\},$ $$

Then we have $P(\mathcal{E}^{\mathrm{cnt}})\geq 1-\delta/4$.

###### Proof.

This is Lemma 3 of Ménard et al. (). See Ménard et al. () for a detailed proof.
∎

When we condition on $\mathcal{E}^{\mathrm{cnt}}$, we have

$$ $\displaystyle\frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a)}$ $\displaystyle\leq\frac{\log(4HTS^{2}A/\delta)+\log(12SAH/\delta)}{n_{h}^{t}(s, a)+\log(12SAH/\delta)}\leq\frac{2\log(12HTS^{2}A/\delta)}{n_{h}^{t}(s,a)+\log( 12SAH/\delta)}$ $\displaystyle\leq\frac{4\log(12HTS^{2}A/\delta)}{\bar{n}_{h}^{t}(s,a)}.$ $$

Therefore, by (B.12), we have

$$ $\displaystyle\mathbb{E}_{\overline{\pi}^{t+1}}\left[\max_{a\in\mathcal{A}} \left(\overline{Q}^{t}_{h}(s_{h},a)-\underline{Q}^{t}_{h}(s_{h},a)\right)^{2}\right]$ $\displaystyle\leq 920A^{2}H^{4}\mathbb{E}_{\pi^{t+1}}\left[\sum_{h^{\prime}=h} ^{H}\frac{\log(12HTS^{2}A/\delta)}{\bar{n}_{h}^{t}(s,a)}\bigg{|}s_{h}\right].$ $$

Therefore, we have

$$ $\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\overline{\pi}^{t+1}} \left[\max_{a\in\mathcal{A}}\left(\overline{Q}^{t}_{h}(s_{h},a)-\underline{Q}^ {t}_{h}(s_{h},a)\right)^{2}\right]$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}920A^{2}H^{4}\mathbb{E}_{\pi^{t+1 }}\left[\sum_{h^{\prime}=h}^{H}\frac{\log(12HTS^{2}A/\delta)}{\bar{n}_{h^{ \prime}}^{t}(s,a)}\bigg{|}s_{h}\right]$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}920A^{2}H^{5}\mathbb{E}_{\pi^{t+1 }}\left[\frac{\log(12HTS^{2}A/\delta)}{\bar{n}_{h}^{t}(s,a)}\bigg{|}s_{h}\right]$ $\displaystyle\leq 920SA^{3}H^{6}\log(12HTS^{2}A/\delta)\log T,$ $$

which concludes the proof of Lemma B.2.
∎

###### Proof.

###### Lemma B.7 .

###### Proof.

### B.6 Proof of Lemma B.3

###### Proof.

We denote by $n_{h}^{t}(s,a)$ the number of times the state action-pair $(s,a)$ was visited in step $h$ in the first $t$ episodes, $n_{h}^{t}(s,a,s^{\prime})$ the number of times the state action next state -pair $(s,a,s^{\prime})$ was visited in step $h$ in the first $t$ episodes, and define $N_{h}^{t}(s,a,s^{\prime})=n_{h}^{t}(s,a)P_{h}(s^{\prime}\mid s,a)$. By Hoeffding’s inequality, we have

$$ $\displaystyle\mathbbm{1}_{n_{h}^{t}(s,a)>0}\left|\frac{n_{h}^{t}(s,a,s^{\prime })-N_{h}^{t}(s,a,s^{\prime})}{\sqrt{n_{h}^{t}(s,a)}}\right|\leq\sqrt{\log(4HTS ^{2}A/\delta)}$ (B.13) $$

holds for a fix $(t,h,s,a,s^{\prime})\in[T]\times[H]\times{\mathcal{S}}\times\mathcal{A}\times{
\mathcal{S}}$ with probability at least $1-\delta/(2HTS^{2}A)$. By taking a union bound over all $(t,h,s,a,s^{\prime})\in[T]\times[H]\times{\mathcal{S}}\times\mathcal{A}\times{
\mathcal{S}}$, we have (B.13) holds for all $(t,h,s,a,s^{\prime})\in[T]\times[H]\times{\mathcal{S}}\times\mathcal{A}\times{
\mathcal{S}}$ with probability at least $1-\delta/2$. We denote by $\mathcal{E}_{2}$ that (B.13) holds for all $(t,h,s,a,s^{\prime})\in[T]\times[H]\times{\mathcal{S}}\times\mathcal{A}\times{
\mathcal{S}}$. When condition on $\mathcal{E}_{2},$ we have

$$ $\displaystyle\mathbbm{1}_{n_{h}^{t}(s,a)>0}\mathop{\mathrm{TV}}\bigl{(}P_{h}^{ *}(\cdot\mid s,a),P_{h}^{t}(\cdot\mid s,a)\bigr{)}$ $\displaystyle=\sum_{s^{\prime}\in{\mathcal{S}}}\mathbbm{1}_{n_{h}^{t}(s,a)>0} \left|\frac{n_{h}^{t}(s,a,s^{\prime})-N_{h}^{t}(s,a,s^{\prime})}{n_{h}^{t}(s,a )}\right|$ $\displaystyle\leq A\sqrt{\frac{\log(4HTS^{2}A/\delta)}{n_{h}^{t}(s,a)}}.$ $$

We conclude the proof by noticing that $P(\mathcal{E}_{2})\geq 1-\delta/2$.
∎

###### Proof.

### B.7 Proof of Lemma B.4

###### Proof.

We prove this using induction. Lemma B.4 obviously holds when $h=H+1.$ If Lemma B.4 hold for $h+1$, we have

$$ $\displaystyle Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)=r_{h}(s,a)+\sum_{s^{ \prime}\in{\mathcal{S}}}P_{h}^{*}(s^{\prime}|s,a)V^{\star}_{\mathrm{LLM}, \lambda,h+1}(s,a)\geq 0.$ $$

We also have

$$ $\displaystyle Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)=r_{h}(s,a)+\sum_{s^{ \prime}\in{\mathcal{S}}}P_{h}^{*}(s^{\prime}|s,a)V^{\star}_{\mathrm{LLM}, \lambda,h+1}(s,a)\leq 1+\sum_{s^{\prime}\in{\mathcal{S}}}P_{h}^{*}(s^{\prime}| s,a)(H-h)=H-h+1.$ $$

Using the property of constraint optimization, we have

$$ $\displaystyle V^{\star}_{\mathrm{LLM},\lambda,h}(s)=\lambda\log\bigl{(}\sum_{a \in\mathcal{A}}\pi_{h}^{\mathrm{LLM}}(a|s)\exp(Q^{\star}_{\mathrm{LLM},\lambda ,h}(s,a)/\lambda)\bigr{)}.$ $$

since $0\leq Q^{\star}_{\mathrm{LLM},\lambda,h}(s,a)\leq H+1-h$, we have $0\leq V^{\star}_{\mathrm{LLM},\lambda,h}(s)\leq H+1-h$. Therefore, we conclude the proof of Lemma B.4 using induction.
∎

###### Proof.

### B.8 Proof of Lemma B.5

###### Proof.

For $\bm{x}=(x_{1},\ldots,x_{A})^{\top}$ and $\bm{\beta}=(\beta_{1},\ldots,\beta_{A})^{\top}$, we define

$$ $\displaystyle f(\bm{x},\bm{\beta})=\bm{x}^{\top}\bm{\beta}-\lambda\sum_{i=1}^{ A}\beta_{i}\log\frac{\beta_{i}}{\widetilde{\beta}_{i}},\;\;f^{*}(\bm{x})=\max_ {\sum_{i=1}^{A}\beta_{i}=1,\beta_{i}>0}f(\bm{x},\bm{\beta}),\;\;\bm{\beta}^{*} (x)=\mathop{\mathrm{argmax}}_{\sum_{i=1}^{A}\beta_{i}=1,\beta_{i}>0}f(\bm{x}, \bm{\beta}).$ (B.14) $$

We have the following lemma.

###### Lemma B.8 .

We have

$$ $\displaystyle f^{*}(\bm{x})=\lambda\log\bigl{[}\sum_{i=1}^{A}\widetilde{\beta} _{i}\exp(x_{i}/\lambda)\bigr{]},\nabla f^{*}(\bm{x})=\bm{\beta}^{*}(\bm{x}), \beta_{i}(\bm{x})=\frac{\partial}{\partial x_{i}}f^{*}(\bm{x})=\frac{ \widetilde{\beta}_{i}\exp(x_{i}/\lambda)}{\sum_{j=1}^{A}\widetilde{\beta}_{j} \exp(x_{j}/\lambda)}.$ $$

Moreover, we have $\|\nabla f^{*}(\bm{x}_{1})-\nabla f^{*}(\bm{x}_{2})\|_{1}\leq\frac{A}{\lambda}
\|\bm{x}_{1}-\bm{x}_{2}\|_{\infty}$.

###### Proof.

See §B.9 for a detailed proof.
∎

First, we have

$$ $\displaystyle f^{*}(\bm{x})-f^{*}(\bar{\bm{x}})$ $\displaystyle=\nabla f^{*}(\bar{\bm{x}})(\bm{x}-\bar{\bm{x}})++\int_{0}^{1} \Bigl{(}\nabla f^{*}\bigl{(}t\bm{x}+(1-t)\bar{\bm{x}}\bigr{)}-\nabla f^{*}( \bar{\bm{x}})\Bigr{)}^{\top}(\bm{x}-\bar{\bm{x}}){\mathrm{d}}t$ $\displaystyle\leq\nabla f^{*}(\bar{\bm{x}})(\bm{x}-\bar{\bm{x}})++\int_{0}^{1} \|\nabla f^{*}\bigl{(}t\bm{x}+(1-t)\bar{\bm{x}}\bigr{)}-\nabla f^{*}(\bar{\bm{ x}})\Bigr{\|}_{1}\|\bm{x}-\bar{\bm{x}}\|_{\infty}{\mathrm{d}}t.$ $$

By Lemma B.8, we have

$$ $\displaystyle f^{*}(\bm{x})-f^{*}(\bar{\bm{x}})$ $\displaystyle\leq\nabla f^{*}(\bar{\bm{x}})(\bm{x}-\bar{\bm{x}})+\frac{A}{ \lambda}\int_{0}^{1}\|t\bm{x}+(1-t)\bar{\bm{x}}-\bar{\bm{x}}\Bigr{\|}_{\infty} \|\bm{x}-\bar{\bm{x}}\|_{\infty}{\mathrm{d}}t$ $\displaystyle=\nabla f^{*}(\bar{\bm{x}})(\bm{x}-\bar{\bm{x}})+\frac{A}{2 \lambda}\|\bm{x}-\bar{\bm{x}}\|_{\infty}^{2}$ (B.15) $$

We conclude the proof of Lemma B.5 by combining (B.8) with Lemma B.8.
∎

###### Proof.

###### Lemma B.8 .

###### Proof.

### B.9 Proof of Lemma B.8

###### Proof.

By the property of constraint optimization, we have $\frac{\partial}{\partial\beta}f\bigl{(}\bm{x},\bm{\beta}(\bm{x})\bigr{)}=c(1,
\ldots,1)^{\top}$ for some constant $c$. By direct computation, we have

$$ $\displaystyle\frac{\partial}{\partial\beta}f\bigl{(}\bm{x},\bm{\beta}(\bm{x}) \bigr{)}=x-\lambda\log\bm{\beta}+\lambda\log\widetilde{\bm{\beta}}-\lambda(1, \ldots,1)^{\top},$ $$

which implies $\beta_{i}(\bm{x})\propto\widetilde{\beta}_{i}\exp(x_{i}/\lambda)$. Since $\sum_{i=1}^{A}\beta_{i}(\bm{x}\propto)=1$, we have

$$ $\displaystyle\beta_{i}(\bm{x})=\frac{\widetilde{\beta}_{i}\exp(x_{i}/\lambda)} {\sum_{j=1}^{A}\widetilde{\beta}_{j}\exp(x_{j}/\lambda)}.$ (B.16) $$

By the definition of $f^{*}$, we have

$$ $\displaystyle f^{*}(\bm{x})=f(\bm{x},\bm{\beta}_{i}(\bm{x}))$ $\displaystyle=\frac{\sum_{i=1}^{A}x_{i}\widetilde{\beta}_{i}\exp(x_{i}/\lambda )}{\sum_{i=1}^{A}\widetilde{\beta}_{i}\exp(x_{i}/\lambda)}-\frac{\sum_{i=1}^{A }x_{i}\widetilde{\beta}_{i}\exp(x_{i}/\lambda)}{\sum_{i=1}^{A}\widetilde{\beta }_{i}\exp(x_{i}/\lambda)}+\lambda\log\bigl{(}\sum_{i=1}^{A}\widetilde{\beta}_{ i}\exp(x_{i}/\lambda)\bigr{)}$ $\displaystyle=\lambda\log\bigl{(}\sum_{i=1}^{A}\widetilde{\beta}_{i}\exp(x_{i} /\lambda)\bigr{)}.$ (B.17) $$

Combining (B.16) and (B.9), we have $\nabla f^{*}(\bm{x})=\bm{\beta}(\bm{x})$. We define $\Delta=\{\bm{\beta}\mid\sum_{i=1}^{A}\beta_{i}=1,\beta_{i}>0\}$, we have the following lemma.

###### Lemma B.9 .

For any $\bm{x},\bm{\beta}\in\Delta$, we have

$$ $\displaystyle\lambda\sum_{i=1}^{A}\beta_{i}\log\frac{\beta_{i}}{\widetilde{ \beta}_{i}}\geq\lambda\sum_{i=1}^{A}\beta_{i}(\bm{x})\log\frac{\beta_{i}(\bm{x })}{\widetilde{\beta}_{i}}+\bm{x}^{\top}\bigl{(}\bm{\beta}-\bm{\beta}(\bm{x}) \bigr{)}+\frac{\lambda}{2A}\|\bm{\beta}-\bm{\beta}(\bm{x})\|_{1}^{2},$ $$

where $\bm{\beta}(\bm{x})$ is defined in (B.14).

###### Proof.

See §B.10 for a detailed proof.
∎

By Lemma B.9, we have

$$ $\displaystyle\lambda\sum_{i=1}^{A}\beta_{i}(\bm{x}_{2})\log\frac{\beta_{i}(\bm {x}_{2})}{\widetilde{\beta}_{i}}\geq\lambda\sum_{i=1}^{A}\beta_{i}(\bm{x}_{1}) \log\frac{\beta_{i}(\bm{x}_{1})}{\widetilde{\beta}_{i}}+\bm{x}_{1}^{\top}\bigl {(}\bm{\beta}(\bm{x}_{2})-\bm{\beta}(\bm{x}_{1})\bigr{)}+\frac{\lambda}{2A}\| \bm{\beta}(\bm{x}_{2})-\bm{\beta}(\bm{x}_{1})\|_{1}^{2},$ $\displaystyle\lambda\sum_{i=1}^{A}\beta_{i}(\bm{x}_{1})\log\frac{\beta_{i}(\bm {x}_{1})}{\widetilde{\beta}_{i}}\geq\lambda\sum_{i=1}^{A}\beta_{i}(\bm{x}_{2}) \log\frac{\beta_{i}(\bm{x}_{2})}{\widetilde{\beta}_{i}}+\bm{x}_{2}^{\top}\bigl {(}\bm{\beta}(\bm{x}_{1})-\bm{\beta}(\bm{x}_{2})\bigr{)}+\frac{\lambda}{2A}\| \bm{\beta}(\bm{x}_{2})-\bm{\beta}(\bm{x}_{1})\|_{1}^{2},$ $$

which implies

$$ $\displaystyle\frac{\lambda}{A}\|\bm{\beta}(\bm{x}_{2})-\bm{\beta}(\bm{x}_{1}) \|_{1}^{2}\leq(\bm{x}_{1}-\bm{x}_{2})^{\top}\bigl{(}\bm{\beta}(\bm{x}_{1})-\bm {\beta}(\bm{x}_{2})\bigr{)}\leq\|\bm{\beta}(\bm{x}_{2})-\bm{\beta}(\bm{x}_{1}) \|_{1}\|\bm{x}_{1}-\bm{x}_{2}\|_{\infty}.$ $$

Therefore, we have

$$ $\displaystyle\frac{\lambda}{A}\|\bm{\beta}(\bm{x}_{2})-\bm{\beta}(\bm{x}_{1}) \|_{1}\leq\|\bm{x}_{1}-\bm{x}_{2}\|_{\infty},$ $$

which concludes the proof of Lemma B.8
∎

###### Proof.

###### Lemma B.9 .

###### Proof.

### B.10 Proof of Lemma B.9

###### Proof.

Let $\beta_{i}$ be the $i$-th element of $\bm{\beta}$, and $\beta_{i}(\bm{x})$ be the $i$-th element of $\bm{\beta}$. We define $g(\bm{\beta})=\lambda\sum_{i=1}^{A}\beta_{i}\log\frac{\beta_{i}}{\widetilde{
\beta}_{i}}$. By the property of the function $g$, we have

$$ $\displaystyle g(\bm{\beta})-g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}$ $\displaystyle=\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}^{\top}\bigl{(}\bm{ \beta}-\bm{\beta}(\bm{x})\bigr{)}+\sum_{i=1}^{A}\int_{\beta_{i}(\bm{x})}^{ \beta_{i}}\int_{\beta_{i}(\bm{x})}^{u}\frac{\lambda}{v}{\mathrm{d}}v{\mathrm{d }}u.$ $$

Since $\beta_{i}<1$, we have

$$ $\displaystyle g(\bm{\beta})-g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}$ $\displaystyle\geq\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}^{\top}\bigl{(}\bm{ \beta}-\bm{\beta}(\bm{x})\bigr{)}+\lambda\sum_{i=1}^{A}\int_{\beta_{i}(\bm{x}) }^{\beta_{i}}\int_{\beta_{i}(\bm{x})}^{u}1{\mathrm{d}}v{\mathrm{d}}u$ (B.18) $\displaystyle=\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}^{\top}\bigl{(}\bm{ \beta}-\bm{\beta}(\bm{x})\bigr{)}+\frac{\lambda}{2}\sum_{i=1}^{A}|\beta_{i}( \bm{x})-\beta_{i}|^{2}$ $\displaystyle\geq\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}^{\top}\bigl{(}\bm{ \beta}-\bm{\beta}(\bm{x})\bigr{)}+\frac{\lambda}{2A}\|\bm{\beta}(\bm{x})-\bm{ \beta}\|_{1}^{2}.$ $$

By the definition of the function $g$, we have

$$ $\displaystyle\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}=(\lambda\log\beta_{1}+ \lambda-\lambda\log\widetilde{\beta}_{1},\ldots,\lambda\log\beta_{A}+\lambda- \lambda\log\widetilde{\beta}_{A})^{\top}.$ (B.19) $$

By the definition of $\bm{\beta}(\bm{x})$ in (B.14), we can easily obtain

$$ $\displaystyle\beta_{i}(\bm{x})=\frac{\widetilde{\beta}_{i}\exp(x_{i}/\lambda)} {\sum_{i=1}^{A}\widetilde{\beta}_{i}\exp(x_{i}/\lambda)}.$ (B.20) $$

Combining (B.19) with (B.20), we have

$$ $\displaystyle\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}=\bm{x}+\lambda\Bigl{(} 1-\log\bigl{(}\sum_{i=1}^{A}\widetilde{\beta}_{i}\exp(x_{i}/\lambda)\bigr{)} \Bigr{)}(1,1,\ldots,1)^{\top}.$ $$

Therefore, we have

$$ $\displaystyle\bigl{(}\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}-\bm{x}\bigr{)} ^{\top}\bigl{(}\bm{\beta}-\bm{\beta}(\bm{x})\bigr{)}$ $\displaystyle\quad\quad=\lambda\Bigl{(}1-\log\bigl{(}\sum_{i=1}^{A}\widetilde{ \beta}_{i}\exp(x_{i}/\lambda)\bigr{)}\Bigr{)}(1,1,\ldots,1)^{\top}\bm{\beta}- \lambda\Bigl{(}1-\log\bigl{(}\sum_{i=1}^{A}\widetilde{\beta}_{i}\exp(x_{i}/ \lambda)\bigr{)}\Bigr{)}(1,1,\ldots,1)^{\top}\bm{\beta}(\bm{x}).$ $$

By the definition of the region $\Delta$ in Lemma B.8, we have $(1,1,\ldots,1)^{\top}\bm{\beta}=(1,1,\ldots,1)^{\top}\bm{\beta}(\bm{x})=1$. Therefore, we have

$$ $\displaystyle\bigl{(}\nabla g\bigl{(}\bm{\beta}(\bm{x})\bigr{)}-\bm{x}\bigr{)} ^{\top}\bigl{(}\bm{\beta}-\bm{\beta}(\bm{x})\bigr{)}=0.$ (B.21) $$

We conclude the proof of Lemma B.9 by combining (B.18) and (B.21).
∎

###### Proof.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: Refer to the weaknesses mentioned above.

Additionally, the RAP framework utilizes MCTS for Blocksworld tasks, also use MC sampling and "likelihood of action" as a reward, similar to the approach in Eq. 5.1 of this paper. Given these similarities, what is the primary reason for the substantial performance advantage of SLINVIT over RAP?
soundness: 2
strengths: 1. This paper introduces a novel approach to improve sample efficiency in RL by integrating LLMs, avoiding the need for fine-tuning the LLM and demonstrating superior performance compared to prompt-engineering methods, such as reflextion and ReAct.
2. It provides structured sub-goals for tasks in ALFWorld, with fine-grained value estimation that supports effective task-solving.
3. The paper includes a theoretical analysis of the relationship between KL divergence and policy performance, offering insights that an LLM policy closer to the optimal policy can help solve RL tasks more efficiently.
summary: Large language models (LLMs) have demonstrated remarkable proficiency in language understanding and generation. However, they are limited in exploration and self-improvement for planning tasks, as they lack autonomous refinement based on feedback. This paper explores how leveraging the policy prior from LLMs can enhance the sample efficiency of reinforcement learning (RL) algorithms.
weaknesses: 1. The implementation details of value-based methods are unclear. Section 5.2 mentions rule-based and Monte Carlo (MC) value estimates, but neither aligns directly with traditional value-based RL algorithms. Additionally, it is unclear which methods were applied to specific benchmarks, and the study lacks ablation analysis for different value estimation methods.
2. Although the paper provides a theoretical analysis of the connection between KL divergence and the policy performance bound, it would benefit from an empirical demonstration of this relationship, even on a simple tabular task. To achieve this, the KL divergence between the LLM and the optimal policy, as well as the value difference between the LLM-guided policy and the optimal policy, should be provided.
3. The motivation for aligning the learned policy with the LLM (e.g., maximizing -KL as in Eq. 3.2) is unclear. In traditional RL (e.g., TRPO), a KL constraint is used to ensure robust learning, so further clarification on why adding a kl divergence is desirable would strengthen this paper.
4. The explanation of simplifying KL divergence as the probability of \(\pi^{LLM}\) is insufficient. It would be helpful to discuss why this simplification maintains equivalence to the original KL and to explore its potential impact.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 1
questions: 1. Where is Eq. 3.1 taken from? It is presented as a specific choice of the author but it is surely defined in a different theoretical context.
2. I assume that the LINVIT is the theoretical motivation of SLINVIT, however it cannot act as so if it's not empirically validated. Have you tried running LINVIT in a tabular reinforcement learning setting? How can we know if the methodology is sound?
3. The rule-based method requires a human review, how is this process handled? Do you have guidelines on how this should be done? What if the LLMs proposed a value function that looks wrong but it correctly compiles?
soundness: 2
strengths: - The empirical results shows that the proposed methodology outperforms the chosen baselines.
- The proposed methodology is evaluated on multiple benchmarks.
summary: The paper aims improve sample efficiency of reinforcement learning by incorporating prior knowledge from LLMs with a novel regularization technique for the policy and value function inspired by entropy-regularized MDPs.
weaknesses: 1. The structure of the paper makes it hard to follow since it jumps from the theoretical justification of the method to the presentation of the results to then go back to a somewhat related theoretical result. A better division of the theory and practice would make the paper easier to follow.
2. The proposed methodology is particularly weak as one version (**rule-based**) strictly requires a human review each time the agent is run and the other (**Monte Carlo**) is not effectively evaluated as the number of sample is set to 1 in the experiments.
3. Theorem 6.2 is a generic proof that is not particularly relevant to the proposed methodology but rather to approximation errors.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Following the weaknesses,
- Can authors provide more practival motivations? Besides, it seems that the provided algorithm highly relies on value-based RL algorithms, does such insight also make sense when leaverage policy-based methods such as PPO?
- What the techinical contribution/hardness in theoretical analysis?

Also, here's some additional question
- At the end of theoretical analysis, it is claimed that ``the core objective of our theoretical analysis is to justify the use of log-probability as regularization", but SLINVIT uses $\pi_{\rm LLM}$ rather thatn $\log\pi_{\rm LLM}$. Why there's a mismatch? Also, could author provide more elaborations on the connection between KL regularization and practical sum of log probabilities?
- (Minor) What's the difference between notations $\mathbb{P}_{\rm LLM}$ and $\pi_{\rm LLM}$, are these the same?
- (Minor) Is the $a$ missing in $\bar{Q}_h^t(s,a)$ for (3.4)?
soundness: 3
strengths: - This paper provide a new perspective of using LLM to improve the sample efficiency of standard RL methods, which does no require the LLM policy to be optimal. The information-theoretical algorithm, LINVIT, provide a provable guarantee which is favorable.
- Due to hardness in optimization objective in LINVIT, this paper also provide a practical version by replacing the entropy regularizer by directly adding the LLM policy, which provides a practically efficient the algorithm
- Both the theoretical and practical result is quite satisfying, showing that the proposed method is effective.
summary: The study introduces
- an information-theoretic alggorithm, LINVIT, which uses LLMs as a regularization factor to enhance the sample efficiency of RL
- a practical version called SLINVIT, simplifying value function construction and using sub-goals to minimize search complexity

Instead of directly using LLMs for decision-making, LINVIT leverages them to refine policy estimation, particularly improving performance when the LLM-provided policy is close to the optimal policy. This approach reduces the data required for learning while retaining the ability to reach the optimal policy even when the LLM policy is suboptimal. Empirical validation in benchmarks like ALFWorld, InterCode, and BlocksWorld shows that LINVIT and SLINVIT significantly outperform traditional RL and LLM methods in terms of sample efficiency and success rates.
weaknesses: - The experiment focuses on the text-based decision problem which LLM is good at, but its performance on more general interative decision-making with abstract state and action is unclear, e.g., solve specific bandit/MDP
- The theory seems standard in analysis of entropy-regularized RL algorithms

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 4
questions: While the paper introduces an interesting concept, it requires significant improvements, particularly in experimental design, explanation of baselines, and addressing concerns about practicality before it can be considered ready for publication.

It is currently unclear if a fair comparison was made to baselines, how it would perform without RL, how it would perform with a sub-optimal LLM policy, how domain-specific it is, how practical the code production and human review is relative to other methods, and whether it could be applied in other environments. 

Further minor comments:
- The title should probably be "How can LLMs guide..." instead of "How can LLM guide"
- The paper mentions several times that (e.g. line 49) that "RL agents require huge amounts of random interactions", which comes across as the authors assume that any RL agent uses random action selection for exploration, even though there are much more sophisticated exploration techniques in the literature that do not explore just randomly. 
- In line 99 you have the term $V^t_{h+1}(s')$ where $t$ was never defined in the text so I think this is an error you'd like to be aware of.
- In line 108 "the LLM policy is hard to be optimal" should be rephrased.
- Line 110 "priorin" spelling error
- Algorithm 1: I would suggest including where the LLM contributes to the algorithm as it is your main contribution, even if it is with a comment in line 3 of the algorithm.
- It would be nice to have some more details on how exactly you are learning a transition model, this was not very clear to me from the paper.
- In order to measure how optimal the LLM policy is in the given environment, it may be helpful to execute a pure LLM policy for one episode. Based on the accumulated reward, a weighting of the regularization term could be determined.
soundness: 2
strengths: - The presentation of the paper is excellent, with informative figures and algorithms.
- The concept of using LLMs indirectly for regularization is a novel and interesting idea.
- The authors provide a theoretical framework to motivate their decision to introduce this technique, which could serve as a foundation for future work of incorporating LLM priors into RL.
- The authors conducted various experiments to evaluate their proposed methodology.
summary: In this paper the authors propose to integrate LLMs within the RL framework by introducing a regularization technique that is based on the KL-divergence between the RL agent's policy and the LLM's policy. This method is coined as Language-INtegrated Value Iteration (LINVIT), and the authors introduce a simplified version of it called SLINVIT for empirical evaluation. Under the assumption that the LLM policy is near-optimal, the authors show that this regularization can yield substantial sample efficiency gains for RL agents in several text-based benchmarks.
weaknesses: - One major concern is that the applicability of the approach is heavily reliant on the LLM policy being essentially (close to) equivalent to the optimal policy. This raises several other concerns. 
   - First, the authors argue in line 125 "Moreover, we can still identify the optimal policy for the original MDP even if the LLM's policy is suboptimal", but there are no experiments in the paper showing what happens when the LLM policy is suboptimal.
  -  Nor is any experiment conducted that shows how a baseline LLM policy would perform without the RL agent, nor of the RL agent without LLM regularization. 
  - It is likely that if the LLM policy is suboptimal, the performance of the RL agent will be hindered rather than enhanced, which limits the applicability of this approach to environments where the LLM policy is (near) optimal. 
  - The authors argue that you need the RL component to be able to adapt and deal with environment feedback, but it seems like the method is only desirable in cases where you have an LLM policy that is almost optimal (which seems like a relatively vague assumption that is not quantifiable in most cases). 
- Another concern is that although the paper admits that SLINVIT simplifies the algorithm described in the theoretical section, these simplifications—such as using BFS and single-rollout Monte-Carlo estimation—aren’t well-justified. There’s a disconnect between the theoretical guarantees provided in the KL divergence analysis and the seemingly substantial simplifications made in the experiments where the algorithm is actually implemented.
- In section 5.2 one of the simplifications introduces a process that makes the LLM write python code for functions that yield some value corresponding to a state in the environment. This python code is then subject to a 'one-time human review', which seems like a major impracticality of using this algorithm. Could this review not be done with an LLM as well perhaps to achieve automation?
- The motivations in the experimental section are also rather unclear
  - A brief explanation of the baselines used (e.g., whether they rely on human interventions, purely LLM-driven policies, or RL-based techniques) and how they differ from SLINVIT would help in assessing the fairness of the experiments, as it is currently unclear.
   - The authors introduce an ablation study for the number of Monte-Carlo samples, showing that $M=2$ performs better than $M=1$, yet they proceed to use $M=1$ in the experiments without a clear justification.