Reason for Future, Act for Now: A Principled Architecture for Autonomous LLM Agents

Thank you for your review. We address your concerns as follows.

W1 Compare the novelty and performance of RAFA with Traditional RL agents (PETS, Planet, and Plan2Explore); Present tasks are too simple, and traditional RL can handle them.

A for W1 From the theoretical perspective, our analysis is aimed at discussing the theoretical performance of our proposed LLM mechanisms (RAFA), where we adopt the analysis tools from the Thomspon sampling (PSRL) in RL. Besides, our sample complexity analysis extends the present PSRL to an infinity horizon setting beyond the linear structure assumption, which is still missing in the current literature. Since we want to interpret the theoretical performance of LLM agents, it is important to let the analysis accommodate general function approximation. For the linear setting, we also refine the analysis in the previous literature ([6, 7]), which assumes a bounded reward while considering the reward to be Gaussian distributed. On the other hand, we claim that our major contribution is not on PSRL but on orchestrating reasoning (learning and planning) and acting following the principled approach in RL. Please see the Appendix A for more detailed discussions. Empirically, we do not need to update the parameter nor sample a parameter from the posterior as PETS, Planet, and Plan2Explore. LLM agent makes an implicit Bayesian inference via In-Context learning, which enables LLM agents to achieve good performance with a few interactions. Since our proposed method is a refinement of previously proposed LLM mechanisms, we use the same large language model for a fair comparison. We also add the citations to the work that you mentioned in Appendix A of the updated manuscript.

W2 Numerical verification of Assumption 4.1 and discussion of the effect when Assumption 4.1 fails in practice.

A for W2 We remark that we can extend our analysis to accommodate cases where LLM approximates the posterior within an error margin $\iota$, resulting in a bounded additional regret of $\iota \cdot T$. Importantly, our novel RAFA algorithm (Algorithm 1) stands distinctly from prevalent LLM mechanisms ([1], [2], [3], [4]), and our analysis, guided by Algorithm 3 and Assumption 4.1, only elucidates the theoretical performance of RAFA.

Besides, we conduct two experiments to numerically verify Assumption 4.1. Since the predictions given by posterior sampling have the contraction property and the variance heterogeneity, we examine these two properties of LLM predictions in multiple settings to study if the distribution of LLM predictions matches the one given by posterior sampling.

Experiment 1. We test if GPT-3 can make an implicit Bayesian inference for the linear regression problem. We first generate i.i.d. data $\{(x_i,y_i)\}^N_{i = 1}$ from $x_i \sim \mathcal{N}(0.8,1),\ y_i\sim \mathcal N(0.5x_i,0.04)$. Then, we feed the following prompt to GPT-3 API (temperature=1.0, top_p=0.8, these parameter configurations can be found in [7]) to obtain 200 predictions when $x_{\text{pred}} = 1$. Specifically, the prompts are "The following data is for linear regression: $(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N), (1.000000,$". Then, we plot the histogram of the LLM-generated predictions and the density function of the calculated $y_{\text{pred}}$ by posterior sampling, where we choose the prior of the coefficient as $\mathcal N(0,0.5)$. We report the results in Figure 8 of the updated manuscript. We find that the histogram of LLM predictions approximately matches the theoretical distribution of the prediction given by the posterior sampling, which supports Assumption 4.1. Also, with an increasing number of generated data, the variance of LLM predictions decays, which shows the contraction property. We also examine variance heterogeneity in the two-dimensional Bayesian linear regression setting. The variance heterogeneity of predictions helps LLMs give more diverse answers when the current prompt contains less relevant information. RAFA relies on the diversity of LLM predictions to guarantee the exploration for those states less explored, hence we wish the variance of LLM predictions for the less explored states is higher. Please check more details and results in Appendix D of the updated manuscript.

Thank you for your review. We address your concerns as follows.

Q1 and W1 No verification of Assumption 4.1. How is the posterior sampling accomplished?

A for Q1 and W1 First, we want to clarify that Assumption 4.1 casts LLM's In-Context Learning as an implicit Bayesian inference, which finds support in various existing literature [1], [2], [3]. To reinforce its theoretical foundation, we have rigorously verified Assumption 4.1 in Appendix D, outlining the requisite regularity conditions and justifications for each. Furthermore, we extend our analysis to accommodate cases where LLM approximates the posterior within an error margin $\iota$, resulting in a bounded additional regret of $\iota \cdot T$. Importantly, our novel RAFA algorithm (Algorithm 1) stands distinct from prevalent LLM mechanisms ([4], [5], [6], [7]), and our analysis, guided by Algorithm 3 and Assumption 4.1, only elucidates the theoretical performance of RAFA. Besides, we conduct two experiments to numerically verify Assumption 4.1. For more details, please see the first argument in the General Response.

W2 MCTS can also be implemented in a closed-loop manner.

A for W2 It is true that MCTS can be implemented in a closed-loop manner to converge for a deterministic environment, which is studied in [8]. However, there is no work that studies how to incorporate closed-loop MCTS with LLMs. Besides, it is still unclear if the closed-loop can achieve a $\sqrt T$ Bayesian regret, as the sample complexity bound in [8] is $\tilde{O} ((1/\epsilon)^d)$ but RAFA only requires $\tilde{O}((1/\epsilon)^2)$ samples to achieve the average $\epsilon$ accuracy, where $d$ is the dimension of the state space. The key difference between RAFA and the closed-loop MCTS is the method of model and critic learning. \textt{RAFA} utilizes ICL to learn the unknown world model and generalizes to the unseen states, which leads to a more efficient exploration and a sharpened regret upper bound.

Q2 How does the RAFA framework tackle the challenge of efficient exploration in its operations?

A for Q2 Since we cast the ICL of LLMs as an implicit Bayesian inference, RAFA explores the environment via the internal randomness of the LLM responses, which is similar to the posterior sampling methods. We also conduct additional experiments to better understand the connections between the randomness of LLM predictions and the exploration of the environment. Specifically, in the ALFWorld environment, the model LLM is prompted to predict the observation of a certain action "go to countertop 1". In Figure 9 of the updated manuscript, we report the diversity of LLM predictions. We find that as more action-observation paris are added to the GPT-3 prompt when timestep increases, the number of distinct prediction responses decreases, i.e., the model LLM has decreasing uncertainty of what objects a certain place has after observing the locations of objects at other places. This corresponds to a decreasing entropy, indicating that the variance heterogeneity of predictions LLMs gives more diverse answers when the current prompt contains less relevant information. In other words, RAFA relies on the diversity of LLM predictions to guarantee the exploration for those states less explored. For more setup details and the results, please refer to Appendix D in the updated manuscript.

[1] Zhang, Yufeng, et al. "What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization." arXiv preprint arXiv:2305.19420 (2023).

[2] Lee, Jonathan N., et al. "Supervised Pretraining Can Learn In-Context Reinforcement Learning." arXiv preprint arXiv:2306.14892 (2023).

[3] Hollmann, Noah, et al. "Tabpfn: A transformer that solves small tabular classification problems in a second." arXiv preprint arXiv:2207.01848 (2022).

[4] Yao, Shunyu, et al. "Tree of thoughts: Deliberate problem solving with large language models." arXiv preprint arXiv:2305.10601 (2023).

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

[6] Shinn, Noah, Beck Labash, and Ashwin Gopinath. "Reflexion: an autonomous agent with dynamic memory and self-reflection." arXiv preprint arXiv:2303.11366 (2023).

[7] Sun, Haotian, et al. "AdaPlanner: Adaptive Planning from Feedback with Language Models." arXiv preprint arXiv:2305.16653 (2023).

[8] Shah, Devavrat, Qiaomin Xie, and Zhi Xu. "Non-asymptotic analysis of monte carlo tree search." Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems. 2020.

I sincerely thank the authors for their hard work on the revision and additional experiments. They certainly addressed some of my concerns (e.g., token efficiency). The new verification (in particular, ALFworld) for Assumption 4.1, while still limited, at least provides some amount of evidence that LLM can do something similar to posterior sampling. I think the paper would be a lot stronger if this is done more thoroughly but I understand it's hard to do some in such short period of time. For example, I would like to see a head-to-head comparison on a simple RL task of LLM and actual posterior sampling (e.g., Figure 9). I would also somewhat disagree that the extension from finite horizon case to infinite horizon case is as signifianct as the authors claim, since one can apply the $\frac{1}{1-\gamma}$ horizon argument for the infinite horizon case (although this is a more subjective opinion). Not to mention that the all of the tested environment's horizons are very short.

More importantly, the formatting of the paper is still unacceptable. Margins are violated in pg 2, 8, and 9. On page 9, the top line of the ICLR template is completely missing and everythinhg is still crampped together. Even to make this little space for a conclusion, the authors removed the anonymous author region from the first page. Per ICLR guideline, the final paper does not have an additional page for the camera ready so there is no way that this paper will fit within 9 pages in its current form. Page limit exists for a reason and I would encourage the authors to adhere to the guidelines. In this current sate, I cannot in good conscience recommend acceptance, but I would consider raising my score to 6 if the author can at least make the paper follow the format guideline.

Thank you for your review. We address your concerns as follows.

W1 This paper is less innovative in RL and lacks discussions with PSRL.

A for W1 From the theoretical perspective, our analysis is aimed at discussing the theoretical performance of our proposed LLM mechanisms (RAFA), where we adopt the analysis tools from the Thomspon sampling (PSRL) in RL. Besides, our sample complexity analysis extends the present PSRL to an infinity horizon setting beyond the linear structure assumption, which is still missing in the current literature. Since we want to interpret the theoretical performance of LLM agents, it is important to let the analysis accommodate general function approximation. For the linear setting, we also refine the analysis in the previous literature ([1, 2]), which assumes a bounded reward while considering the reward to be Gaussian distributed. On the other hand, we claim that our major contribution is not on PSRL but on orchestrating reasoning (learning and planning) and acting following the principled approach in RL. Please see the Appendix A for more detailed discussions. Empirically, we do not need to update the parameter nor sample a parameter from the posterior. LLM agent makes an implicit Bayesian inference via In-Context learning, which enables LLM agents to achieve good performance with a few interactions. Since our proposed method is a refinement of previously proposed LLM mechanisms, we use the same large language model for a fair comparison.

W2 This paper also lacks numerical verification of Assumption 4.1.

A for W2 We conduct two experiments to numerically verify Assumption 4.1. Since the predictions given by posterior sampling have the contraction property and the variance heterogeneity, we examine these two properties of LLM predictions in multiple settings to study if the distribution of LLM predictions matches the one given by posterior sampling.

Experiment 1. We test if GPT-3 can make an implicit Bayesian inference for the linear regression problem. We first generate i.i.d. data $[(x_i,y_i)]^N_{ i = 1}$ from $x_i \sim \mathcal{N}(0.8,1), y_i\sim \mathcal N(0.5x_i,0.04)$. Then, we feed the following prompt to GPT-3 API (temperature=1.0, top_p=0.8, these parameter configurations can be found in [7]) to obtain 200 predictions when $x_{\text{pred}} = 1$. Specifically, the prompts are "The following data is for linear regression: $(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N), (1.000000,$". Then, we plot the histogram of the LLM-generated predictions and the density function of the calculated $y_{\text{pred}}$ by posterior sampling, where we choose the prior of the coefficient as $\mathcal N(0,0.5)$. We report the results in Figure 8 of the updated manuscript. We find that the histogram of LLM predictions approximately matches the theoretical distribution of the prediction given by the posterior sampling, which supports Assumption 4.1. Also, with an increasing number of generated data, the variance of LLM predictions decays, which shows the contraction property. We also examine variance heterogeneity in the two-dimensional Bayesian linear regression setting. The variance heterogeneity of predictions helps LLMs give more diverse answers when the current prompt contains less relevant information. RAFA relies on the diversity of LLM predictions to guarantee the exploration for those states less explored, hence we wish the variance of LLM predictions for the less explored states is higher. Please check more details and results in Appendix D of the updated manuscript.

I thank the authors for the clarification, the manuscript revision, and the new experiments. If the information gain is indeed novel, then I think it would be a good addition to the literature. Since I am not an expert in this area, I will defer this judgment to others.

The last page is still a bit rough but at least there are no egregious formatting violations anymore. The additional experiments (in particular contextual bandits) instill some confidence that LLMs can do posterior sampling in this case although it is evident that there is a visible gap.

As promised, I will raise my score to 6. However, I still strongly recommend that the authors make the last page more readable, and take other reviewers' feedback into consideration. I wish the authors the best of luck.

Thank you for your review. We address your concerns as follows.

Q1 What are the empirical results under a single LLM model?

A for Q1 We have compared our proposed method (RAFA) with Reflexion [1] in all four experiments in this paper, where Reflexion only uses a single LLM with closed-loop interactions. Results can be found in Section 5 and Appendix G. We observed that Reflexion improves much slower compared to RAFA and has an inferior final performance. This is because Reflexion is an oversimplified version of RAFA, where the planning subroutine revises the current action to maximize the reward function (“reason for now”) instead of planning multiple future steps to maximize the value function (“reason for future”), which measures the expected cumulative future reward. Besides, in the ALFWorld environment, we compared RAFA and AdaPlanner [2], which is also a baseline that uses a single LLM model. We found that AdaPlanner has a higher initial performance due to a handcrafted set of programs for rejecting suboptimal candidate trajectories, which, however, is challenging to construct without the domain knowledge of a specific task. Besides, its final success rate is also lower than RAFA. In the BlocksWorld and Tic-Tac-Toe environments, we compared RAFA with the Chain-of-Thought and GPT-4 baselines, respectively. The results showed that RAFA outperforms these baselines by a remarkable margin.

Q2 How many repetitions did you use for the empirical results? Do the results vary that much if you have more?

A for Q2 We follow a similar reporting procedure as previous LLM work (such as [2], [3], and [4]) and do not repeat the experiments multiple times. The reason behind this choice is that the results do not vary too much, as opposed to experiments for reinforcement learning methods. How the Bayesian perspective is connected to the Model-Predictive Control-based algorithm.

Q3 and W1 Is there a way to avoid the complete disconnect between theory and practice? This paper assumes the access to the true posterior and ignores anything about the underlying models. How to connect

A for Q3 and W1 First, we want to clarify that Assumption 4.1 casts LLM's In-Context Learning as an implicit Bayesian inference, which finds support in various existing literature [3], [4], [5]. In Appendix D in the manuscript, we prove that Assumption D.1. holds when we pose several regularity conditions on the model and data-generating process. Furthermore, we extend our analysis to accommodate cases where LLM approximates the posterior within an error margin $\iota$, resulting in a bounded additional regret of $\iota \cdot T$. Importantly, our novel RAFA algorithm (Algorithm 1) stands distinctly from prevalent LLM mechanisms ([1], [2], [6], and [7]), and our analysis, guided by Algorithm 3 and Assumption 4.1, only elucidates the theoretical performance of RAFA.

Besides, we conduct two experiments to numerically verify Assumption 4.1. Since the predictions given by posterior sampling have the contraction property and the variance heterogeneity, we examine these two properties of LLM predictions in multiple settings to study if the distribution of LLM predictions matches the one given by posterior sampling.

Experiment 1. We test if GPT-3 can make an implicit Bayesian inference for the linear regression problem. We first generate i.i.d. data $[(x_i,y_i)]^N_{i = 1}$ from $x_i \sim \mathcal{N}(0.8,1),\ y_i\sim \mathcal N(0.5x_i,0.04)$. Then, we feed the following prompt to GPT-3 API (temperature=1.0, top_p=0.8, these parameter configurations can be found in [7]) to obtain 200 predictions when $x_{\text{pred}} = 1$. Specifically, the prompts are "The following data is for linear regression: $(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N), (1.000000,$". Then, we plot the histogram of the LLM-generated predictions and the density function of the calculated $y_{\text{pred}}$ by posterior sampling, where we choose the prior of the coefficient as $\mathcal N(0,0.5)$. We report the results in Figure 8 of the updated manuscript. We find that the histogram of LLM predictions approximately matches the theoretical distribution of the prediction given by the posterior sampling, which supports Assumption 4.1. Also, with an increasing number of generated data, the variance of LLM predictions decays, which shows the contraction property. We also examine variance heterogeneity in the two-dimensional Bayesian linear regression setting. The variance heterogeneity of predictions helps LLMs give more diverse answers when the current prompt contains less relevant information. RAFA relies on the diversity of LLM predictions to guarantee the exploration for those states less explored, hence we wish the variance of LLM predictions for the less explored states is higher. Please check more details and results in Appendix D of the updated manuscript.

2. Comparison with RL and Posterior Sampling. From the theoretical perspective, our analysis is aimed at discussing the theoretical performance of our proposed LLM mechanisms (RAFA), where we adopt the analysis tools from the Thomspon sampling (PSRL) in RL. Besides, our sample complexity analysis extends the present PSRL to an infinity horizon setting beyond the linear structure assumption, which is still missing in the current literature. Since we want to interpret the theoretical performance of LLM agents, it is important to let the analysis accommodate general function approximation. For the linear setting, we also refine the analysis in the previous literature ([10,11]), which assumes a bounded reward while considering the reward to be Gaussian distributed. On the other hand, we claim that our major contribution is not on PSRL but on orchestrating reasoning (learning and planning) and acting following the principled approach in RL. Please see the Appendix A for more detailed discussions. Empirically, we do not need to update the parameter nor sample a parameter from the posterior. LLM agent makes an implicit Bayesian inference via In-Context learning, which enables LLM agents to achieve good performance with a few interactions. Since our proposed method is a refinement of previously proposed LLM mechanisms, we use the same large language model for a fair comparison.

3. Format Issue We acknowledge the feedback regarding formatting and are committed to optimizing the paper's readability. In the updated manuscript, we condensed the content to maintain clarity while ensuring the paper's coherence and comprehensiveness. We also added a conclusion section to help readers get the gist quickly.

4. An additional metric other than sample complexity for evaluation. To evaluate the performance of RAFA in a more profound way, we also consider other metrics like token complexity for evaluation. We compare the token efficiency of our method on the Game of 24 with various baseline methods and the results are shown in Appendix G.1 of the updated manuscript. RAFA is superior in terms of token complexity. Methods that lack planning like Reflexion have a low token demand, however, it is not enough to compensate for the drop in performance. Methods that lack in-context learning like Tree of Thoughts would generate unnecessary repeated trials due to lack of reflection and improvement, which makes the method token inefficient.

[1] Zhang, Yufeng, et al. "What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization." arXiv preprint arXiv:2305.19420 (2023).

[2] Lee, Jonathan N., et al. "Supervised Pretraining Can Learn In-Context Reinforcement Learning." arXiv preprint arXiv:2306.14892 (2023).

[3] Yao, Shunyu, et al. "Tree of thoughts: Deliberate problem solving with large language models." arXiv preprint arXiv:2305.10601 (2023).

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

[5] Shinn, Noah, Beck Labash, and Ashwin Gopinath. "Reflexion: an autonomous agent with dynamic memory and self-reflection." arXiv preprint arXiv:2303.11366 (2023).

[6] Sun, Haotian, et al. "AdaPlanner: Adaptive Planning from Feedback with Language Models." arXiv preprint arXiv:2305.16653 (2023).

[7] Gruver, Nate, et al. "Large language models are zero-shot time series forecasters." arXiv preprint arXiv:2310.07820 (2023).

[8] Hollmann, Noah, et al. "Tabpfn: A transformer that solves small tabular classification problems in a second." arXiv preprint arXiv:2207.01848 (2022).

[9] Han, Chi, et al. "In-Context Learning of Large Language Models Explained as Kernel Regression." arXiv preprint arXiv:2305.12766 (2023).

[10] Lu, Xiuyuan, and Benjamin Van Roy. "Information-theoretic confidence bounds for reinforcement learning." Advances in Neural Information Processing Systems 32 (2019).

[11] Russo, Daniel, and Benjamin Van Roy. "Learning to optimize via posterior sampling." Mathematics of Operations Research 39.4 (2014): 1221-1243.