CoPS: Empowering LLM Agents with Provable Cross-Task Experience Sharing

## Abstract

Abstract Sequential reasoning in agent systems has been significantly advanced by large language models (LLMs), yet existing approaches face limitations. Reflection-driven reasoning relies solely on knowledge in pretrained models, limiting performance in novel scenarios, while experience-assisted reasoning often depends on external experiences and lacks clear principles for selecting representative experiences. We address these limitations by proposing CoPS ( C r o ss-Task Ex p erience S haring), a generalizable algorithm that enhances sequential reasoning by cross-task experience sharing and selection. In detail, CoPS leverages agents’ experiences on previous tasks, selecting distribution-matched experiences via a provable pessimism-based strategy to maximize utility while minimizing risks from distribution shifts. Extensive experimental results on benchmarks like Alfworld, Webshop, and HotPotQA demonstrate that CoPS consistently outperforms state-of-the-art baselines, with superior sample efficiency suitable for resource-constrained scenarios. Theoretically, we show that the performance of our algorithm depends on both the quality of the pretrained LLM and the matching between the agent’s task-dependent trial distribution and that generated by the LLM. Our work bridges the gap between existing sequential reasoning paradigms and validates the effectiveness of leveraging cross-task experiences, shedding light on the potential to improve agents’ generalization and adaptability across diverse tasks. Our codes are available at https://github.com/uclaml/COPS .

## 1 Introduction

Burgeoning agent systems driven by advanced large language models (LLMs, (Devlin et al., ; Brown et al., ; OpenAI, ; Hu et al., )) have demonstrated remarkable capabilities in solving complex tasks through sequential reasoning (Qin et al., ; Hao et al., ; Huang et al., ; Chen et al., , ; Li et al., ). These agent systems employ two typical sequential reasoning paradigms: reflection-driven reasoning and experience-assisted reasoning. Reflection-driven reasoning leverages a model’s internal capabilities through methods such as reflection (Shinn et al., ), long-term rollouts (Zhou et al., ), or chain-of-thought (CoT) reasoning (Wei et al., ). While this approach capitalizes on the knowledge within the pre-trained model, it faces notable limitations. Specifically, relying solely on existing knowledge in the pre-trained model to generate rationales restricts the model’s performance when encountering novel scenarios. Moreover, there is an increased risk of hallucinations, where internal reasoning may lead to plausible but incorrect responses (Huang et al., ). These challenges highlight the need for integrating external experiences to enhance the agent’s sequential reasoning capabilities.

In contrast, experience-assisted sequential reasoning utilizes retrieval-based methods that enable the agent to interact with a memory bank of experiences, allowing the model to overcome knowledge cutoffs, personalize responses, and reduce hallucinations. However, these experiences are often manually curated or sourced from expert models (Raparthy et al., ), which is resource-intensive and poses scalability issues. Additionally, experience-assisted reasoning often lacks clear principles for selecting representative examples (Kagaya et al., ), potentially underutilizing the value of past experiences. These limitations bring us to a critical research question:

Figure: Figure 1: A brief illustration of CoPS, which fully leverages agents’ cross-task experiences to enhance sequential reasoning by sharing and selecting distribution-matched experiences from previous task trajectories.
Refer to caption: x1.png

Can agent systems enhance sequential reasoning by sharing and selecting cross-task experiences?

To address this question, we propose CoPS (Cross-Task Experience Sharing), a theoretically grounded algorithm that empowers agent systems through cross-task experience sharing and selection. CoPS demonstrates its generalizability by working effectively in both settings: utilizing fully external experiences in the *offline* setting and leveraging completely self-derived experiences in the *online* setting. By utilizing representative cross-task experiences, CoPS enables agents to improve performance on new, complex sequential reasoning tasks. Our key contributions are summarized as follows:

- •
We introduce CoPS, a method that fully leverages agents’ cross-task experiences to enhance sequential reasoning by selecting distribution-matched experiences from previous task trajectories. Central to our approach is a theoretically grounded experience selection strategy based on the pessimism principle, which aims to maximize the utility of successful, representative experiences while minimizing risks associated with distribution shifts from out-of-distribution samples. Notably, CoPS is agnostic to the agent’s base model, task type, experience sources, and implementation framework, making it easy-to-use and generalizable across various settings.
- •
Experimentally, we validate CoPS on key benchmarks such as Alfworld (Shridhar et al., ), Webshop (Yao et al., ), and HotPotQA (Yang et al., ). CoPS consistently outperforms state-of-the-art experience-assisted reasoning approaches like RAP (Kagaya et al., ) and reflection-driven reasoning methods, like Reflexion (Shinn et al., ) and LATS (Zhou et al., ). Moreover, CoPS demonstrates superior sample efficiency compared to resource-intensive methods like LATS, making it highly suitable for resource-constrained scenarios. These results showcase CoPS’s effectiveness in practical applications.
- •
Theoretically, we show that in both offline and online settings, the performance of our pessimism-based algorithm depends on both the quality of the pre-trained LLM and the matching between the cross-task experience distribution decided by the trials selected by the agent, and a task-dependent experience distribution denoted by the LLM. Our findings shed light on general strategies for designing efficient experience sharing and selction algorithms and offer a comprehensive understanding of CoPS’s effectiveness across different scenarios.

Notations
We denote by $[n]$ the set $\{1,\dots,n\}$. For two positive sequences $\{a_{n}\}$ and $\{b_{n}\}$ with $n=1,2,\dots$, we write $a_{n}=O(b_{n})$ if there exists an absolute constant $C>0$ such that $a_{n}\leq Cb_{n}$ holds for all $n\geq 1$ and write $a_{n}=\Omega(b_{n})$ if there exists an absolute constant $C>0$ such that $a_{n}\geq Cb_{n}$ holds for all $n\geq 1$. We use $\widetilde{O}(\cdot)$ to further hide the polylogarithmic factors. We use $(x_{i})_{i=1}^{n}$ to denote sequence $(x_{1},...,x_{n})$, and we use $\{x_{i}\}_{i=1}^{n}$ to denote the set $\{x_{1},...,x_{n}\}$.
We use ${\text{D}_{\text{H}}}(p,q)=\sqrt{1/2\cdot\int(\sqrt{p}-\sqrt{q})^{2}}$ to denote the Hellinger distance. We use ${\text{D}_{\text{TV}}}(p,q)=1/2\cdot\int|p-q|$ to denote the Total variation distance. We use $\chi^{2}(p,q)=\int p^{2}/q-1$ to denote the chi-square distance. For two sentences $a$ and $b$, we use $a|b$ to denote the sentence formed by concatenating $a$ and $b$. We use $\Delta(\mathcal{D})$ to denote the set of distributions over $\mathcal{D}$.

## 2 Related Work

### 2.1 LLM-powered Agents

In recent years, there has been a significant surge in research focused on LLM-powered agents (Chen et al., , ; Chan et al., ). React (Yao et al., ) laid the foundation for much of the subsequent work on LLM agents, particularly those based on in-context learning (ICL). The most relevant studies to CoPS include Shinn et al. (); Kagaya et al. (); Zhou et al. (); Raparthy et al. (). In Kagaya et al. (), a retrieval process for selecting in-context demonstrations was proposed. However, their approach depends on frequent embedding queries during the planning stage, leading to inefficiency issues even in smaller LLM settings. Additionally, RAP manually splits the agent’s planning trajectory into multiple stages for each trial, with benchmark-specific tailoring, significantly increases implementation complexity and raises scalability concerns. Zhou et al. () introduced a Tree-of-Thought (ToT) approach (Yao et al., ), incorporating backpropagation and a valuation process. However, their approach demonstrated poor sample efficiency, making it less suited for real-world agent settings where opportunities for trial and error are limited. Similarly, Liu et al. () integrated value-based search into a theoretical framework, but faced similar challenges with sample efficiency. Feng et al. () explored fine-tuning for specific LLM agent tasks, achieving good performance but with high computational costs. Lastly, Raparthy et al. () utilized high-quality experiences as ICL demonstrations for sequential reasoning. Although achieving remarkable performance, these experiences are introduced from external RL systems, which is resource-intensive and poses scalability issues.

### 2.2 In-context Demonstrations Selection

The selection of demonstrations for ICL has been widely studied. Wang et al. () approached in-context demonstration selection from a Bayesian perspective, explicitly constructing a latent variable for the selection process. However, their analysis did not account for the pre-trained knowledge distribution, and their results were primarily empirical. Yan et al. () investigated the impact of repetition in in-context demonstrations, conducting controlled experiments to assess how repetitions in pre-trained knowledge influence results. Scarlatos and Lan () developed a reinforcement learning framework to select in-context examples, while Voronov et al. () examined the impact of prompt formatting on in-context learning performance. Additionally, Shum et al. () introduced an automatic CoT augmentation and selection method for ICL example datasets. Hu et al. () analyzed the scaling of in-context demonstrations from a theoretical standpoint, deriving general statistical bounds while accounting for pre-training errors. However, their focus was primarily on CoT in general ICL settings, not on the specific challenges faced by LLM agents interacting with environments and requiring feedback for optimization.

### 2.3 Theory of Agents

Several works have advanced the theoretical understanding of LLM agents.
He et al. () explored the statistical theory of LLM agents through the lens of Bayesian aggregated imitation learning. Lin et al. () provided a theoretical analysis of transformers within the context of in-context reinforcement learning. Wang et al. () examined the training and generalization of transformers for sequential reasoning, drawing parallels between transformer behavior and online learning algorithms. Sumers et al. () offered a cognitive perspective on LLM agents, while Park et al. () investigated the regret of LLM agents in sequential reasoning tasks, contributing both theoretical and empirical insights that inform CoPS’s development.

## 3 Methodology

### 3.1 Preliminary

We consider a sequential decision-making scenario, consisting of a task space $\mathtt{M}$, a state space $\mathtt{S}$, and an action space $\mathtt{A}$. The state $s\in\mathtt{S}$ is defined as a descriptive sentence representing the history of the current task. For example: “You are in the middle of a room. Please find a path to reach the apple.” The action $a\in\mathtt{A}$ is a solution to the task, such as: “Move right. The apple is on the table.” The agent interacts with the environment through trials. At the beginning of each trial, a task $\mathbf{M}$ is randomly drawn from the task space, $\mathbf{M}\sim\mathbb{P}^{\mathtt{M}}$. The agent then observes an initial state $s_{1}$, sampled from the initial state distribution, $s_{1}\sim\mathbb{P}^{\mathbf{M}}_{0}$. At each step $h$, the agent makes a decision $a_{h}$ based on the current state $s_{h}$, and the next state is updated as $s_{h+1}=s_{h}|a_{h}$. The agent either successfully completes the task or continues generating actions until reaching the maximum number of interactions $H$ between the agent and the environment. We define an *experience* $\tau$ as a complete trial, i.e., $\tau=s_{h}$, where $h\leq H$ is the final step of the current trial. The reward $r(s_{h})$ denotes how effectively the experience solves the task, with $0\leq r(s_{h})\leq 1$.

In this work, we assume access to a large language model (LLM) to assist in decision-making. We represent the LLM as ${\text{LLM}}(a|\cdot)$, a conditional distribution of actions given the input sequence.

Figure: Algorithm 1 CoPS: Cross-Task Experience Sharing

### 3.2 Proposed Method

We introduce our proposed method, CoPS, based on distribution matching. CoPS operates on a trial-wise basis, making it suitable for both the *offline setting*, where the agent has access to an external static dataset containing experiences, and the *online setting*, where the agent gathers experiences through interactions with the environment. Suppose our agent is at the start of a trial with an initial state $s_{1}\sim\mathbb{P}_{0}^{\mathbf{M}}$. We introduce the key components of CoPS as follows.

Memory Bank The agent has access to a memory bank $\mathcal{D}$ containing experiences, either from a pre-collected dataset (offline) or from previous experiences (online). We do not impose restrictions on $\mathcal{D}$, meaning that experiences in $\mathcal{D}$ exhibit great diversity. Specifically, an experience $\tau\in\mathcal{D}$ may correspond to different tasks $\mathbf{M}$ or to varying solution strategies for the same task. Our goal is to develop a strategy for retrieving experiences from $\mathcal{D}$ that assist in decision-making for the current task.

Cross-Task Experience Sharing CoPS utilizes an external module called the *decoder*, denoted as ${\mathtt{Dec}}$ in Line 1. In general, the decoder outputs a task-dependent distribution of experiences conditioned on the initial state $s_{1}$, reflecting how the LLM would solve the task $\mathbf{M}$ associated with $s_{1}$ without explicit instructions. With the decoder’s help, the agent’s goal is to find a probability distribution $\widehat{p}$ over all experiences in $\mathcal{D}$ that satisfies:

$$ $\displaystyle\widehat{p}=\mathop{\mathrm{argmax}}_{p\in\Delta(\mathcal{D})} \mathbb{E}_{\tau\sim p}[r(\tau)]-d(p,{\mathtt{Dec}}(\cdot|s_{1})),$ (3.2) $$

where $d$ is a metric over distributions. Intuitively, (3.2) is similar to the *pessimism principle*, commonly used in offline RL literature (Jin et al., ). The goal of $\widehat{p}$ is to maximize the expected reward while keeping the distribution close to the one decoded by ${\mathtt{Dec}}$. Importantly, $\widehat{p}$ supports the cross-task setting, as it does not restrict its support to experiences from the same task as $s_{1}$. For a given in-context memory size $k$, CoPS repeatedly samples experiences $\tau^{1},\dots,\tau^{k}$ from $\widehat{p}$, as shown in Line 3.

Execution Planning Let $\mathcal{T}=\tau^{1}|\dots|\tau^{k}$ represent the *experience collection* containing $\tau^{1},\dots,\tau^{k}$. Starting from the initial state $s_{1}$, the agent executes actions step-by-step, where each action $a_{h}$ is drawn from the LLM’s distribution, conditioned on both the experience collection and the current state:

$$ $a_{h}\sim{\text{LLM}}(\cdot|{\mathcal{T}},s_{h}).$ $$

In the online setting, after completing a trial, the agent updates the memory bank $\mathcal{D}$ by adding the new experience for future use.

Implementation Details Here we discuss several implementation details for CoPS. *First*, in practice, directly computing the distance $d(p,{\mathtt{Dec}}(\cdot|s_{1}))$ between distributions in (3.2) is computationally intractable. Therefore, we use an empirical approximation to translate the distance between distributions into the distance between experiences drawn from those distributions, as shown in (3.1). *Second*, we specify the choice of ${\mathtt{Dec}}$. The decoder outputs an experience $\tau^{s_{1}}$ from $\mathcal{D}$ that starts with the same initial state $s_{1}$. If multiple such experiences exist, we select the most recent one. This $\tau^{s_{1}}$ naturally reflects the behavior of the LLM for solving the task starting from $s_{1}$ without intervention. *Third*, we discuss how to approximately solve (3.1) since enumerating all possible distributions in $\Delta(\mathcal{D})$ is computationally inefficient. Specifically, we define the distance function $d$ and approximately solve $\widehat{p}$ as follows:

$$ $d(\tau,\tau^{\prime}):=c\cdot\text{cos}(e(\tau),e(\tau^{\prime})),\ \widehat{p }(\tau)\propto r(\tau)\cdot\exp(-d(\tau,\tau^{s_{1}})),$ (3.3) $$

where $c\geq 0$ is a hyperparameter, “cos” denotes the cosine function, and $e$ is an embedding function that maps a language sentence to a high-dimensional Euclidean space. In practice, we use $e$ as a language embedding model (e.g., gte-Qwen2 7b (Li et al., )). This approach favors selecting successful experiences from $\mathcal{D}$ with probabilities proportional to the inverse distance from the current initial state $s_{1}$. The hyperparameter $c$ in (3.3) controls the influence of relative distances: when $c=0$, the method uniformly samples successful experiences from $\mathcal{D}$, and as $c\to\infty$, it deterministically selects the experience closest to $\tau^{s_{1}}$.

## 4 Experiments

In this section, we present our experimental study evaluating the practical performance of CoPS on real-world LLMs, specifically the Llama 3.1 models (Dubey et al., ). Our results show that CoPS achieves state-of-the-art (SOTA) performance in both task success rate and sample efficiency, surpassing existing baselines to the best of our knowledge. A detailed description of our prompt formulation is provided in Appendix C. Notably, CoPS is both simple to implement and generalizable across different environments: for each trial, the selected experiences are straightforwardly added to the prompts, requiring no manual modifications.

This prompting strategy offers two distinct advantages: first, it significantly boosts sequential reasoning performance by incorporating cross-task experiences, outperforming reflection-driven methods like Reflexion. Second, the prompts across trials share a substantial prefix, which maximizes the effectiveness of prefix-caching mechanisms in modern LLM-serving systems (Zheng et al., ), leading to significant efficiency improvements over RAP (Kagaya et al., ).

Benchmarks We evaluate our algorithms on three representative benchmarks: Alfworld (Shridhar et al., ), Webshop (Yao et al., ), and HotPotQA (Yang et al., ). In these benchmarks, agents strive to solve problems in limited number of trials, enabling cross-trial and cross-task experience sharing. In Alfworld, agents are provided with a specific task description within a simulated household environment, interacting through predefined actions and receiving feedback in the form of textual descriptions. In Webshop, the agent must locate a product that matches user specifications from a catalog of over one million items, interacting with the HTML page and search engine while receiving limited product information per trial. In HotPotQA, the agent answers complex questions requiring specific knowledge, using Wikipedia to retrieve relevant articles. In all benchmarks, the reward function $r(\tau)$ is defined as $1$ if the agent successfully completes the task and 0 0 otherwise.

LLM Selection We conduct our entire experiment with the widely-used Llama 3.1 series of models (Dubey et al., ), in consideration of their superior benchmark performance and the sustainability of open-weight LLM ecosystems(^1^11Note that these are a bunch of representative and popular open source models (Wang et al., ; He et al., ; Xiao et al., ; Hu et al., ) can be considered. We choose the latest model at our experiment time due to resource limitations.). Specifically, our experiments are conducted with Llama 3.1 8b Instruct and Llama 3.1 70b Instruct on NVIDIA A6000 and A100 GPUs. We use gte-Qwen2 7b Instruct (Li et al., ) as our embedding model. We use SGLang (Zheng et al., ) as our LLM-serving engine for its SOTA serving performance and prefix-caching mechanism.

Baselines We compare CoPS with three representative baselines: Reflexion (Shinn et al., ), RAP (Kagaya et al., ), and LATS (Zhou et al., ). In Reflexion, the agent try to solve the task in each environment over multiple trials until it succeeds. After each failed attempt, the LLM agent reflects on its unsuccessful trajectory and saves this reflection in its memory. For each subsequent trial, the agent is provided with up to three recent reflections from the same task. In RAP, at each stage within a trial, the agent is presented with the top-$k$ search results of trajectory fragments as in-context demonstrations. In LATS, the agent utilizes a tree-structured search to explore multiple reasoning and action rationales at each trial. When it encounters failed rationales, the agent generates reflections on its mistakes and integrates these insights into its decision-making process for future trials.

### 4.1 Results and Analysis

In this section, we demonstrate that CoPS outperforms all baselines across all benchmarks and model sizes, considering both sample efficiency and task success rate. Detailed performance illustrations over multiple trials are presented in Figure LABEL:fig:allresult. Our hyperparameter details are provided in Table 5 in Appendix B.

**Table 1: Performance comparison of Reflexion, RAP, and CoPS on Alfworld benchmark using Llama3.1 8b and 70b models.**
| Algorithm | Performance |  |
| --- | --- | --- |
| Llama3.1 8b | Llama3.1 70b |  |
| Reflexion (^2^22The original codebase of Reflexion struggles to perform on most tasks with the smaller Llama3.1 8b model. This is primarily because the model tends to repeat the same action, leading to task failure. To mitigate this, we introduced a resampling mechanism to enhance Reflexion performance, which activates when the model begins to repeat actions. This modification significantly improved Reflexion’s performance.) | 86 | 94 |
| RAP | 70 | 93 |
| CoPS | 94 | 100 |

Alfworld Benchmark Table 2 and Figures LABEL:alf:8b, LABEL:alf:70b illustrate the comparison between CoPS, Reflexion, and RAP on the Alfworld benchmark. The values represent the success rate after 10 trials across 134 tasks. When using the smaller Llama 3.1 8b model, CoPS reaches a success rate of 94%, significantly surpassing both Reflexion (86%) and RAP (70%). This result is particularly noteworthy because Reflexion requires the much larger Llama 3.1 70b model to achieve similar performance, highlighting superior effectiveness of CoPS. This demonstrates CoPS’s ability to achieve state-of-the-art performance even with limited computational resources and less capable models, offering a clear advantage over other algorithms. Furthermore, when scaling to the larger Llama 3.1 70b model, CoPS achieves a perfect success rate of 100%. These results emphasize that CoPS scales effectively, consistently outperforming the baselines across model sizes. Although RAP also leverages an in-context demonstrations retrieval mechanism, it lacks an effective experiences selection algorithm, thus noticeably underperforms CoPS. Additionally, it is important to note that RAP manually splits the agent’s planning trajectory into multiple stages for each trial, and these split methods are specific to each benchmark and must be manually tailored. This significantly increases implementation complexity and introduces scalability issues. In contrast, CoPS efficiently reuses successful experiences by directly placing them in the prompts, without requiring benchmark-specific modifications, making it a more practical and flexible solution. As a result, CoPS not only surpasses the baselines in performance but also offers out-of-the-box usability by eliminating the need for manual intervention.

**Table 2: Performance comparison of Reflexion, RAP, LATS, and CoPS on Webshop benchmark using Llama3.1 8b and 70b models.**
| Algorithm | Performance |  |
| --- | --- | --- |
| Llama3.1 8b | Llama3.1 70b |  |
| Reflexion | 30 | 30 |
| RAP | 42 | 42 |
| LATS | 24 | 32 |
| CoPS | 50 | 56 |

Webshop Benchmark(^3^33We observed that scaling up the model sizes for Reflexion and RAP on the Webshop benchmark did not result in significant improvements. This observation aligns with the original findings of Reflexion (Shinn et al., , Appendix B.1) and RAP (Kagaya et al., , Table 2), which suggest that these models tend to converge on local minima that require highly creative strategies to overcome.) Table 2 and Figures LABEL:web:8b, LABEL:web:70b compare the performance of CoPS with all baseline algorithms on the Webshop benchmark, measured in terms of success rate. The values indicate the success rate over 50 products, with each algorithm evaluated through 10 trials per product. For the smaller Llama 3.1 8b model, CoPS achieves a success rate of 50%, outperforming the next best competitor, RAP, by a substantial absolute improvement of 8%. When scaling to the larger Llama 3.1 70b model, the performance gain of CoPS becomes even more pronounced, with a success rate of 56%. This marks a 14% absolute improvement over RAP.

To ensure a fair comparison across the baselines, we modified the LATS baseline by reducing the width of the search tree and limiting the number of trajectory iterations. This adjustment ensures that the running time spent on each baseline is approximately equal. Even with these changes, LATS still exhibits significantly lower sample efficiency. Specifically, the total number of tokens generated by Llama 3.1 8b in LATS (1,555,365 tokens) is nearly five times greater than that in CoPS (314,336 tokens). Further details can be found in Table 3. This discrepancy in token usage highlights the inefficiency of current search-tree-based algorithms. In contrast, CoPS demonstrates much better efficiency and performance under the same inference constraints.

**Table 3: Token generation count for each of the Webshop experiments. It’s worth notice that for each models the LATS token generation count is at least 5 times to CoPS.**
| Algorithm | Reflexion | RAP | LATS | CoPS |
| --- | --- | --- | --- | --- |
| Llama3.1 8b | 159131 | 107504 | 1555365 | 314336 |
| Llama3.1 70b | 125406 | 109245 | 1058752 | 113849 |

**Table 4: Performance comparison of Reflexion, LATS, and CoPS on HotPotQA benchmark using Llama3.1 8b and 70b models.**
| Algorithm | Performance |  |
| --- | --- | --- |
| Llama3.1 8b | Llama3.1 70b |  |
| Reflexion | 56 | 61 |
| LATS | 55 | 64 |
| CoPS | 63 | 65 |

HotPotQA Benchmark Table 4 and Figures LABEL:hot:8b, LABEL:hot:70b illustrate the comparison between CoPS, Reflexion, and LATS on the HotPotQA benchmark, conducted on 100 question-answering (QA) tasks. The values in the table represent the success rates, with each algorithm being tested over 10 trials. As evidenced by the results, CoPS consistently achieves superior performance relative to both Reflexion and LATS across all model sizes. The advantage of CoPS is particularly evident when using the smaller Llama 3.1 8b model, where CoPS achieves a success rate of 63%, outperforming Reflexion and LATS by substantial absolute improvements of 7% and 8%, respectively. Moreover, even when scaled up to the larger Llama 3.1 70b model, CoPS continues to gain stronger performance. In this setting, CoPS reaches a success rate of 65%, surpassing Reflexion by 4% and LATS by 1%. Note that both Reflexion and LATS baselines demonstrate a significant performance gap when shifting from smaller to larger model, while the results for CoPS is relatively consistent and maintains the performance edge throughout different sizes of models. This demonstrates that CoPS’s principled cross-task experience sharing mechanism also excels in tasks requiring complex reasoning.

Conclusion Our experiments across Alfworld, Webshop, and HotPotQA demonstrate that CoPS consistently outperforms state-of-the-art baselines in both task success rate and sample efficiency. Notably, CoPS achieves superior performance even with smaller models like Llama 3.1 8b, highlighting its efficiency and practicality for resource-constrained scenarios. These results validate the effectiveness of leveraging principled cross-task experiences sharing through our theoretically grounded selection strategy, confirming that CoPS enhances sequential reasoning capabilities across diverse tasks and model sizes.

### 4.2 Ablation Study

In this section, we analyze how two key hyperparameters affect the performance of CoPS: the scaling factor $c$ in Equation (3.3) and the number of in-context experiences $k$ placed at the beginning of prompts. We conducted experiments on the Alfworld benchmark using both Llama 3.1 8b and Llama 3.1 70b models.

Scaling factor For the scaling factor $c$, we tested four settings: $c=0$, $1$, $5$ and $10$, while keeping the number of in-context experiences fixed at $k=5$ (see Figures LABEL:ablc:8b and LABEL:ablc:70b). Our findings indicate that for smaller models like Llama 3.1 8b, a small but non-zero value of $c$ (e.g., $c=1$) generally yields better performance (Figure LABEL:ablc:8b). This suggests that moderate scaling effectively balances model adaptability and robustness on less capable models.

Number of experiences Regarding the number of in-context experiences $k$, we evaluated values ranging from $1$ to $10$, setting $c=0$ (see Figures LABEL:ablk:8b and LABEL:ablk:70b). We observed that performance improves as $k$ increases up to $k=3$, after which it plateaus for both model sizes. This result indicates that while increasing the in-context experience size enhances performance to a point, adding more than three experiences may not offer substantial gains.

Our ablation study reveals that tuning key hyperparameters in CoPS is crucial for optimal performance. Specifically, for smaller models, a small but non-zero scaling factor $c$ (e.g., $c=1$) effectively balances adaptability and robustness. Additionally, increasing the number of in-context experiences $k$ enhances performance up to $k=3$, beyond which additional experiences offer minimal gains. These insights provide practical guidance for hyperparameter selection, ensuring that CoPS can be efficiently deployed across various settings to maximize its sequential reasoning capabilities.

## 5 Theoretical Framework of Experience-Assisted Agents

In this section, we develop the theoretical framework to demonstrate the effectiveness of CoPS. For simplicity, we analyze our algorithm in a bandit setting, where the maximum number of steps for each experience is $H=1$. Slightly different from the formulation in Section 3, we define an experience as $\tau=s|a|r$, consisting of an initial state $s$, an action $a$, and its reward $r=r(s,a)$.

We introduce additional notations for clarity in our analysis. Let ${\mathcal{T}}=\tau_{1}|\tau_{2}|\dots$ denote the experience collection. The length of ${\mathcal{T}}$ is denoted by $|{\mathcal{T}}|$, i.e., ${\mathcal{T}}=(\tau_{1},...,\tau_{|{\mathcal{T}}|})$. We use ${\mathcal{T}}_{t}$ to represent the first $t$ steps of the experience collection, i.e., ${\mathcal{T}}_{t}=\tau_{1}|\dots|\tau_{t}$. For any experience collection ${\mathcal{T}}$, we assume $|{\mathcal{T}}|\leq T$. We define $\mathtt{T}$ as the space of all trajectories, and $\mathtt{T}_{t}$ as the space of trajectories of length $t$. We denote a general algorithm as $\text{Alg}(\cdot|\cdot,\cdot,\cdot):\mathtt{M}\times\mathtt{T}\times\mathtt{S}
\rightarrow\Delta(\mathtt{A})$, which takes as input a task $\mathbf{M}\in\mathtt{M}$, an experience collection ${\mathcal{T}}\in\mathtt{T}$, and a state $s\in\mathtt{S}$, and outputs a distribution over actions $a\in\mathtt{A}$. Note that some algorithms may not use the task $\mathbf{M}$ as input, in which case we write $\text{Alg}(\cdot|\cdot,\cdot)$. We denote $\mathbb{P}^{\mathbf{M},\text{Alg}}_{t}$ as the distribution over the first $t$ steps of an experience collection under task $\mathbf{M}$ and algorithm Alg. For an algorithm Alg that takes $\mathbf{M},{\mathcal{T}},s$ as input, we define its *posterior average* as $\overline{\text{Alg}}(\cdot|{\mathcal{T}},s)=\mathbb{E}_{\mathbf{M}\sim\mathbb
{P}^{\mathtt{M}}(\cdot|{\mathcal{T}}^{\prime}={\mathcal{T}},s^{\prime}=s)}[
\text{Alg}(\cdot|\mathbf{M},{\mathcal{T}}^{\prime},s^{\prime})]$, which is the best Bayesian approximation of Alg given the experience collection ${\mathcal{T}}$ and current state $s$.

### 5.1 LLM Pretraining

We begin by describing the pretraining process for the LLM. Let ${\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s):\mathtt{T}\times
\mathtt{S}\rightarrow\Delta(\mathtt{A})$ represent an LLM agent that outputs a distribution over $\mathtt{A}$, where $\widehat{\bm{\theta}}\in\bm{\Theta}$ is the parameter of the LLM, $\bm{\Theta}$ denotes the whole parameter space. We assume that there exists a pretraining dataset $\mathcal{D}_{\text{pre}}=\{{\mathcal{T}}^{1},\dots,{\mathcal{T}}^{{n_{\text{
pre}}}}\}$, with $|{\mathcal{T}}^{i}|=T-1$. Following the pretraining setup in Lin et al. (), we assume two algorithms: a *context algorithm*, ${\text{Alg}^{C}}(\cdot|\cdot,\cdot):\mathtt{T}\times\mathtt{S}\rightarrow
\Delta(\mathtt{A})$, and an *expert algorithm*, ${\text{Alg}^{E}}(\cdot|\cdot,\cdot,\cdot):\mathtt{M}\times\mathtt{T}\times
\mathtt{S}\rightarrow\Delta(\mathtt{A})$. In general, the context algorithm provides a “natural” action based on the experience collection and current state, while the expert algorithm provides a more informed action, given the task information, experience collection, and current state. Since the expert algorithm has access to task information $\mathbf{M}$, it typically produces better actions than the context algorithm.

We now describe the pretraining process. To generate an experience collection ${\mathcal{T}}=\tau_{1}|\dots|\tau_{T-1}\in\mathcal{D}_{\text{pre}}$, we first sample a task $\mathbf{M}\sim\mathbb{P}^{\mathtt{M}}$. For each experience $\tau_{i}$, the state is sampled from the initial state distribution $s_{i}\sim\mathbb{P}^{\mathbf{M}}_{0}$, the action is sampled using the context algorithm $a_{i}\sim{\text{Alg}^{C}}(\cdot|{\mathcal{T}}_{i-1},s_{i})$, and the reward is given by $r_{i}=r(s_{i},a_{i})$. After generating the experience collection, we collect expert feedback $\bar{a}_{1},\dots,\bar{a}_{T-1}$ for each step of ${\mathcal{T}}$, using the expert algorithm, where $\bar{a}_{i}\sim{\text{Alg}^{E}}(\cdot|\mathbf{M},{\mathcal{T}}_{i-1},s_{i})$. Repeating this process ${n_{\text{pre}}}$ times produces the trajectories ${\mathcal{T}}^{i}$ and expert actions $\bar{a}_{1}^{i},\dots,\bar{a}_{T-1}^{i}$ for $i\in[{n_{\text{pre}}}]$. Finally, we pretrain the LLM ${\text{Alg}_{\widehat{\bm{\theta}}}}$ by solving the following maximum likelihood estimation problem:

$$ $\displaystyle\widehat{\bm{\theta}}\leftarrow\mathop{\mathrm{argmax}}_{\bm{ \theta}\in\bm{\Theta}}\sum_{i=1}^{{n_{\text{pre}}}}\sum_{t=1}^{T}\log\text{Alg }_{\bm{\theta}}(\bar{a}_{t}^{i}|{\mathcal{T}}^{i}_{t-1},s_{t}^{i}).$ $$

For the remainder of this paper, we use ${\text{Alg}_{\widehat{\bm{\theta}}}}$ to represent our LLM. Below, we present several standard assumptions for analyzing ${\text{Alg}_{\widehat{\bm{\theta}}}}$.

###### Definition 5.1 ( Lin et al. 2023 ) .

Let $\bm{\Theta}$ be the set of parameters of the LLM, $\text{Alg}_{\bm{\theta}}$. We call $\bm{\Theta}_{0}\subseteq\bm{\Theta}$ a $\rho$-cover of $\bm{\Theta}$ with respect to $\text{Alg}_{\bm{\theta}}$ if, for any $\bm{\theta}\in\bm{\Theta}$, there exists $\bm{\theta}_{0}\in\bm{\Theta}_{0}$ such that

$$ $\displaystyle\forall s\in\mathtt{S},t\in[T],{\mathcal{T}}\in\mathtt{T}_{t-1}, \|\log\text{Alg}_{\bm{\theta}}(\cdot|{\mathcal{T}},s)-\log\text{Alg}_{\bm{ \theta}_{0}}(\cdot|{\mathcal{T}},s)\|_{\infty}\leq\rho.$ $$

We denote $\mathcal{N}(\rho)=|\bm{\Theta}_{0}|$ as the $\rho$-covering number of $\text{Alg}_{\bm{\theta}}$.

Next assumption assumes that, the best approximation between the trained LLM and the posterior average of the expert algorithm, $\overline{{\text{Alg}^{E}}}$, can be bounded by some constant.

###### Assumption 5.2 ( Lin et al. 2023 ) .

There exists $\bm{\theta}^{*}\in\bm{\Theta}$ and a *model capacity error* ${\epsilon_{\text{real}}}>0$ such that

$$ $\forall t\in[T],\log\mathbb{E}_{\mathbf{M}\sim\mathbb{P}^{\mathtt{M}},s\sim \mathbb{P}_{0}^{\mathbf{M}},{\mathcal{T}}\sim\mathbb{P}_{t-1}^{\mathbf{M},{ \text{Alg}^{C}}},\bar{a}\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s) }\bigg{[}\frac{\overline{{\text{Alg}^{E}}}(\bar{a}|{\mathcal{T}},s)}{\text{Alg }_{\bm{\theta}^{*}}(\bar{a}|{\mathcal{T}},s)}\bigg{]}\leq{\epsilon_{\text{real }}}.$ $$

Finally, we make assumptions for the decoder ${\mathtt{Dec}}$ introduced in Algorithm 1. We assume access to a class of decoders ${\mathtt{Dec}}_{t}:\mathtt{S}\rightarrow\Delta(\mathtt{T}_{t})$ that maps the state $s$ to a distribution over the space of $t$ number of experiences, capable of estimating the distribution $\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{t}({\mathcal{T}})$, which represents the task-dependent experience distribution offered by LLM.

###### Assumption 5.3 .

For the decoder ${\mathtt{Dec}}_{t}:\mathtt{S}\rightarrow\Delta(\mathtt{T}_{t})$, there exists a *decoder coefficient* $C_{{\mathtt{Dec}}}>1$ such that for any $t\in[T],{\mathcal{T}}\in\mathtt{T}_{t-1},\mathbf{M}\in\mathtt{M}$ and $s\sim\mathbb{P}_{0}^{\mathbf{M}}$, we have

$$ $\frac{1}{C_{{\mathtt{Dec}}}^{2}}\leq\frac{{\mathtt{Dec}}_{t-1}({\mathcal{T}}|s )}{\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{t-1}({\mathcal{T}})}\leq C_{{ \mathtt{Dec}}}^{2}.$ $$

###### Definition 5.1 ( Lin et al. 2023 ) .

###### Assumption 5.2 ( Lin et al. 2023 ) .

###### Assumption 5.3 .

### 5.2 Algorithms for the Offline Setting

We consider the same offline setting as in Section 3. Suppose we have an offline dataset $\mathcal{D}$, and the agent is given an initial state $s$. We formalize the experience selection problem as a distribution selection problem, where the agent has access to a candidate set of distributions, denoted by $\mathcal{P}=\{\mathbb{P}^{1}(\cdot|\cdot,\cdot),\dots,\mathbb{P}^{|\mathcal{P}
|}(\cdot|\cdot,\cdot)\}\subseteq 2^{\mathtt{T}_{T-1}\times\mathtt{S}
\rightarrow\Delta(\mathtt{T}_{T-1})}$. Each element in this set represents a mapping from the dataset $\mathcal{D}$ and the current state $s$ to a distribution over trajectories $\mathcal{T}$ of length $T-1$. In general, each $\mathbb{P}^{i}$ can be interpreted as the distribution over all possible combinations of $T-1$ experiences from the dataset $\mathcal{D}$. The agent’s goal is to select a distribution ${\widehat{\mathbb{P}}^{s}}$ from $\mathcal{P}$ that minimizes the suboptimality gap, which quantifies the performance difference between the best possible strategy and the strategy selected by the agent, as measured by the expert algorithm:

$$ $\displaystyle\text{SubOpt}({\widehat{\mathbb{P}}^{s}}):=\mathbb{E}_{\mathbf{M} \sim\mathbb{P}^{\mathtt{M}},s\sim\mathbb{P}_{0}^{\mathbf{M}}}\bigg{[}\max_{{ \widehat{\mathbb{P}}}\in\mathcal{P}}\mathbb{E}_{{\mathcal{T}}\sim{\widehat{ \mathbb{P}}},a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s)}r(s,a)- \mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}^{s}},a\sim\overline{{\text{ Alg}^{E}}}(\cdot|{\mathcal{T}},s)}r(s,a)\bigg{]}.$ (5.1) $$

We propose OfflineCoPS in Algorithm 2, which is an experience collection-based version of CoPS. The core idea of OfflineCoPS mirrors that of CoPS: the agent seeks to find experience collection that maximize the reward while minimizing the distributional shift from the experience collection of the current task, denoted by LLM. Given the test state $s$, OfflineCoPS first runs the decoder to obtain a distribution ${\mathtt{Dec}}_{T-1}(\cdot|s)$, which approximates $\mathbb{P}^{\mathcal{M},{\text{Alg}^{C}}}_{t-1}$. Then, OfflineCoPS applies the *pessimism principle*, as in (3.2). The selected distribution $\mathbb{P}^{*}\in\mathcal{P}$ aims to identify a distribution that produces an experience collection which maximizes the reward given the actions provided by the LLM, while staying close to the decoded distribution ${\mathtt{Dec}}_{T-1}(\cdot|s)$. To measure the distributional distance, we employ the $\chi^{2}$-distance. Similar to the hyperparameter $c$ in CoPS, OfflineCoPS introduces a hyperparameter $\epsilon_{\text{pre}}$ to balance the trade-off between maximizing reward and satisfying the regularity condition imposed by ${\mathtt{Dec}}_{T-1}(\cdot|s)$.

Figure: Algorithm 2 OfflineCoPS

We have the following theorem to characterize the performance of OfflineCoPS.

###### Theorem 5.4 .

By setting

$$ $\displaystyle{\epsilon_{\text{pretrain}}}=C_{{\mathtt{Dec}}}T\cdot\sqrt{5\cdot T \log(\mathcal{N}(1/({n_{\text{pre}}}T)^{2})T)\cdot{n_{\text{pre}}}^{-1}+T{ \epsilon_{\text{real}}}},$ $$

and denote $\mathbb{P}^{*,s}=\mathop{\mathrm{argmax}}_{{\widehat{\mathbb{P}}}\in\mathcal{P
}}\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}(\cdot|\mathcal{D},s),a
\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s)}r(s,a)$, we have the following bound with probability at least $1-2/T$:

$$ $\displaystyle\text{SubOpt}({\widehat{\mathbb{P}}^{s}})\leq 2C_{{\mathtt{Dec}}} {\epsilon_{\text{pretrain}}}\mathbb{E}_{\mathbf{M}\sim\mathbb{P}^{\mathtt{M}}, s\sim\mathbb{P}_{0}^{\mathbf{M}}}\sqrt{1+\chi^{2}(\mathbb{P}^{*,s}(\cdot| \mathcal{D},s),\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T-1}(\cdot))}.$ $$

###### Proof.

See Appendix A.1.
∎

Theorem 5.4 provides several insights into why CoPS achieves superior performance and how experience selection should be tailored under different circumstances:

- •
The final suboptimality gap of the selected distribution $\mathbb{P}^{*,s}$ depends on the decoder coefficient $C_{{\mathtt{Dec}}}$ and the pretraining error parameter $\epsilon_{\text{pre}}$. This implies that for a more powerful LLM, the selected experience distribution $\mathbb{P}^{*,s}$ will be closer to the optimal distribution. Meanwhile, the dependence of $\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T-1}$ suggests that the task-dependent experience collection distribution offered by LLM serves as a strong regularizer to select the optimal retrieval strategy.
- •
The optimal choice of the pretraining error parameter $\epsilon_{\text{pre}}$ is influenced by the decoder coefficient $C_{{\mathtt{Dec}}}$, the number of pretraining trajectories in the pretraining set ${n_{\text{pre}}}$, and the model capacity error $\epsilon_{\text{real}}$. In general, for a more powerful LLM, where ${n_{\text{pre}}}$ is large and $\epsilon_{\text{real}}$ is small, our theorem suggests that the agent should focus more on aligning the selected experience collection distribution $\mathbb{P}^{*,s}$ with the decoder distribution ${\mathtt{Dec}}$. This aligns with our observations in Section 4.2, where smaller models, such as LLaMA 3.1 8b, are more sensitive to the choice of the hyperparameter $c$.

###### Theorem 5.4 .

###### Proof.

### 5.3 Algorithms for the Online Setting

We also consider an analysis for a variant of OfflineCoPS to the online setting. Here, let $\mathcal{P}=\{\mathbb{P}^{1}(\cdot|\cdot,\cdot),\dots,\mathbb{P}^{|\mathcal{P}
|}(\cdot|\cdot,\cdot)\}\subseteq 2^{\mathtt{T}_{t-1}\times\mathtt{S}
\rightarrow\Delta(\mathtt{T}_{t-1})}$ which includes mappings that map an experience collection ${\mathcal{T}}_{t-1}$ and a test state $s$ to a distribution over $\mathtt{T}_{t-1}$. Each $\mathbb{P}^{i}$ can be thought as a strategy to pick the experience collection that depends on the past observations. At step $t$, we have history $\mathcal{H}_{t-1}=\{s_{1},a_{1},r_{1},\dots,s_{t-1},a_{t-1},r_{t-1}\}$. Then the agent receives $s_{t}\sim\mathbb{P}_{0}^{\mathbf{M}_{t}}$, where $\mathbf{M}_{t}\sim\mathbb{P}^{\mathtt{M}}$. Then the agent selects $\mathbb{P}_{t}$ by some algorithm and samples ${\mathcal{T}}_{t-1}\sim\mathbb{P}_{t}(\cdot|\mathcal{H}_{t-1},s_{t})$. Then the agent takes the action $a_{t}\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}}_{t-1},s_{t})$. Her goal is to minimize the following regret:

$$ $\displaystyle\text{Regret}_{T}:=\sum_{t=1}^{T}\mathbb{E}_{\mathbf{M}_{t}\sim \mathbb{P}^{\mathtt{M}},s_{t}\sim\mathbb{P}_{0}^{\mathbf{M}_{t}}}\bigg{[}\max_ {\mathbb{P}^{i}\in\mathcal{P}}\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}_{t- 1}\sim\mathbb{P}^{i}(\cdot|\mathcal{H}_{t-1}),\\ \bar{a}\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}_{t-1},s_{t})\end{ subarray}}r(s_{t},\bar{a})-\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}_{t-1} \sim\mathbb{P}_{t}(\cdot|\mathcal{H}_{t-1}),\\ a_{t}\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}_{t-1},s_{t})\end{ subarray}}r(s_{t},a_{t})\bigg{]}.$ (5.3) $$

We propose the algorithm OnlineCoPS in Algorithm 3. Similar to OfflineCoPS, OnlineCoPS adapts an decoder that takes the current state as its input and outputs a distribution of the experience collection ${\mathcal{T}}$, which aims to estimate the LLM output distribution $\mathbb{P}_{t-1}^{\mathbf{M}_{t},{\text{Alg}^{C}}}$. Unlike OfflineCoPS, the optimization goal of OnlineCoPS in (5.4) is similar to the *optimistic principle* that originates from the online decision-making problems (Abbasi-Yadkori et al., ), which aims to maximize both the reward and the distribution distance between the decoder distribution ${\mathtt{Dec}}_{t-1}$ and the selected one ${\widehat{\mathbb{P}}^{t}}$. Meanwhile, note that the selected experience collection distribution only depends on the past history $\mathcal{H}_{t-1}$, which is small in the early stage of the online decision-making process. We have the following theorem to demonstrate the theoretical guarantee of OnlineCoPS.

Figure: Algorithm 3 OnlineCoPS

###### Theorem 5.5 .

By setting

$$ $\displaystyle{\epsilon_{\text{pretrain}}}=C_{{\mathtt{Dec}}}\cdot T^{2}\cdot \sqrt{5\cdot\frac{T\log(\mathcal{N}(1/({n_{\text{pre}}}T)^{2})T^{2})}{{n_{ \text{pre}}}}+T{\epsilon_{\text{real}}}},$ $$

and denote $\mathbb{P}^{*,t}=\mathop{\mathrm{argmax}}_{\widehat{\mathbb{P}}\in\mathcal{P}}
\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}_{t-1}\sim\widehat{\mathbb{P}}(
\cdot|\mathcal{H}_{t-1},s_{t}),\\
\bar{a}\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}_{t-1},s_{t})\end{
subarray}}r(s_{t},\bar{a})$, we have the following bound holds with probability at least $1-2/T$:

$$ $\displaystyle\text{Regret}_{T}\leq 2C_{{\mathtt{Dec}}}{\epsilon_{\text{ pretrain}}}\sum_{t=1}^{T}\sqrt{1+\chi^{2}(\mathbb{P}^{*,t}(\cdot|\mathcal{H}_{ t-1},s_{t}),\mathbb{P}^{\mathbf{M}_{t},{\text{Alg}^{C}}}_{t-1}(\cdot))}.$ $$

###### Proof.

See Appendix A.2.
∎

Similar to Theorem 5.4 for the offline setting, Theorem 5.5 also shares the following insights.

- •
The regret is controlled by the difference between the best experience collection generated distribution ${\mathbb{P}^{*,t}}$ and the experience collection distribution induced by the contextual algorithm at $t$-th step. Therefore, the best strategy overall is to select trajectories from the history $\mathcal{H}_{t-1}$ that can approximates the current task well to avoid the distribution shift.
- •
With a more powerful LLM, the ${\epsilon_{\text{pretrain}}}$ will be smaller, which means the selected experience collection can approximate the best selection better.

###### Theorem 5.5 .

###### Proof.

## 6 Conclusion, Limitation and Future Work

In this paper, we introduced CoPS (Cross-Task Experience Sharing), a theoretically
grounded algorithm that empowers agent systems with cross-task experiences sharing. Using a pessimism-based strategy to select relevant experiences, CoPS maximizes utility while minimizing the risks of distribution shifts. Our experiments on benchmarks like Alfworld, Webshop, and HotPotQA demonstrate that CoPS outperforms state-of-the-art methods in both success rates and sample efficiency. Theoretically, we show that our algorithm’s performance depends on the LLM’s pre-trained quality and the matching between the cross-task experience distribution decided by the trials selected by the agent, and a task-dependent experience distribution denoted by the LLM, providing insights for improving experience retrieval methods.

While CoPS shows clear improvements over existing methods, it has several limitations. Its effectiveness heavily depends on the quality and diversity of the experiences in the memory bank, meaning that outdated or poorly aligned experiences can reduce its performance. Additionally, CoPS is sensitive to hyperparameters like the scaling factor and the number of in-context experiences, which may require time-consuming tuning that doesn’t always generalize well across different tasks or models. Finally, the theoretical guarantees we provide also rely on assumptions about the accuracy of the decoder and specific pre-training properties of the LLM, which may not always hold in real-world scenarios.

Looking ahead, several research directions could further improve CoPS.
These include developing adaptive hyperparameter tuning methods, exploring dynamic memory management to keep experiences relevant, and adding ways to assess experience quality. Additionally, adapting CoPS for multi-agent systems and integrating it with reinforcement learning could enable collaborative learning and continuous performance improvement. Pursuing these areas will help LLM agents handle even more complex sequential reasoning tasks.

## Appendix A Additional Details in Section 5

### A.1 Proof of Theorem 5.4

We prove Theorem 5.4 here. First, we need the following lemmas.

###### Lemma A.1 (Lemma 20, Lin et al. 2023 ) .

With probability at least $1-\delta$, we have

$$ $\displaystyle\mathbb{E}_{\mathbf{M}\sim\mathbb{P}^{\mathtt{M}},s\sim\mathbb{P} _{0}^{\mathbf{M}},{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T -1}}\bigg{[}\sum_{t=1}^{T}{\text{D}_{\text{H}}}^{2}(\overline{{\text{Alg}^{E}} }(\cdot|{\mathcal{T}}_{t-1},s),{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{ \mathcal{T}}_{t-1},s))\bigg{]}$ $\displaystyle\leq 5\cdot\frac{T\log(\mathcal{N}(1/({n_{\text{pre}}}T)^{2})T/ \delta)}{{n_{\text{pre}}}}+T{\epsilon_{\text{real}}},$ $$

where the covering number $\mathcal{N}$ is defined in Definition 5.1, ${\epsilon_{\text{real}}}$ is defined in Assumption 5.2.

Next lemma is used to provide a per-state guarantee for the generalization error.

###### Lemma A.2 .

Let event ${\mathcal{E}}$ be defined as

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M},{\text{Alg}^{ C}}}_{T-1}}\bigg{[}\sum_{t=1}^{T}{\text{D}_{\text{H}}}^{2}(\overline{{\text{ Alg}^{E}}}(\cdot|{\mathcal{T}}_{t-1},s),{\text{Alg}_{\widehat{\bm{\theta}}}}( \cdot|{\mathcal{T}}_{t-1},s))\bigg{]}\leq m_{c}\bigg{[}c\cdot\frac{T\log( \delta^{-1}\mathcal{N}(1/({n_{\text{pre}}}T)^{2})T)}{{n_{\text{pre}}}}+T{ \epsilon_{\text{real}}}\bigg{]},$ $$

where ${\epsilon_{\text{real}}}$ is defined in Assumption 5.2. Then we have $\mathbb{P}(\mathcal{E})\geq 1-1/m_{c}-\delta$.

###### Proof.

By Markov inequality, we have that with probability at most $1/m_{c}$,

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M},{\text{Alg}^{ C}}}_{T-1}}\bigg{[}\sum_{t=1}^{T}{\text{D}_{\text{H}}}^{2}(\overline{{\text{ Alg}^{E}}}(\cdot|{\mathcal{T}}_{t-1},s),{\text{Alg}_{\widehat{\bm{\theta}}}}( \cdot|{\mathcal{T}}_{t-1},s))\bigg{]}$ $\displaystyle\geq m_{c}\cdot\mathbb{E}_{\mathbf{M}\sim\mathbb{P}^{\mathtt{M}}, s\sim\mathbb{P}_{0}^{\mathbf{M}},{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M},{ \text{Alg}^{C}}}_{T-1}}\bigg{[}\sum_{t=1}^{T}{\text{D}_{\text{H}}}^{2}( \overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}_{t-1},s),{\text{Alg}_{\widehat {\bm{\theta}}}}(\cdot|{\mathcal{T}}_{t-1},s))\bigg{]}.$ $$

Meanwhile, by Lemma A.1, we know that with probability at most $\delta$, we have

$$ $\displaystyle\mathbb{E}_{\mathbf{M}\sim\mathbb{P}^{\mathtt{M}},s\sim\mathbb{P} _{0}^{\mathbf{M}},{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T -1}}\bigg{[}\sum_{t=1}^{T}{\text{D}_{\text{H}}}^{2}(\overline{{\text{Alg}^{E}} }(\cdot|{\mathcal{T}}_{t-1},s),{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{ \mathcal{T}}_{t-1},s))\bigg{]}$ $\displaystyle\geq c\cdot\frac{T\log(\delta^{-1}\cdot\mathcal{N}(1/({n_{\text{ pre}}}T)^{2})T)}{{n_{\text{pre}}}}+T{\epsilon_{\text{real}}}.$ $$

Therefore, by the union bound, we have $\mathbb{P}({\mathcal{E}})\geq 1-\delta-1/m_{c}$.
∎

Now we begin to prove Theorem 5.4.

###### Proof.

We follow the proof steps in Lin et al. (). We suppose that the event ${\mathcal{E}}$ denoted in Lemma A.2 holds. We first bound the difference of reward by the difference between their distribution distance. Let ${\widehat{\mathbb{P}}}$ be an arbitrary distribution over ${\mathcal{T}}$. Then we have

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}(\cdot)}| \mathbb{E}_{a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s)}r(s,a)- \mathbb{E}_{a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s)}r (s,a)|$ $\displaystyle\leq\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}(\cdot)}{ \text{D}_{\text{TV}}}(\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s),{ \text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s))$ $\displaystyle\leq\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}(\cdot)}{ \text{D}_{\text{H}}}(\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s),{\text {Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s)),$ (A.1) $$

the first inequality holds due to the fact $|r|\leq 1$ and the property of TV distance, the second one holds since ${\text{D}_{\text{TV}}}\leq{\text{D}_{\text{H}}}$. Starting from (A.1) we have

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}}{\text{D}_{ \text{H}}}(\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s),{\text{Alg}_{ \widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s))$ $\displaystyle=\mathbb{E}_{{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M},{\text{Alg}^ {C}}}_{T-1}}{\text{D}_{\text{H}}}(\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{ T}},s),{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s))\cdot\frac{ {\widehat{\mathbb{P}}}({\mathcal{T}})}{\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}} }_{T-1}({\mathcal{T}})}$ $\displaystyle\leq\sqrt{\underbrace{\mathbb{E}_{{\mathcal{T}}\sim\mathbb{P}^{ \mathbf{M},{\text{Alg}^{C}}}_{T-1}}{\text{D}_{\text{H}}}^{2}(\overline{{\text{ Alg}^{E}}}(\cdot|{\mathcal{T}},s),{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{ \mathcal{T}},s))}_{I_{1}}}\cdot\sqrt{\underbrace{\mathbb{E}_{{\mathcal{T}}\sim \mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T-1}}\bigg{(}\frac{{\widehat{\mathbb {P}}}({\mathcal{T}})}{\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T-1}({\mathcal {T}})}\bigg{)}^{2}}_{I_{2}}},$ (A.2) $$

where the first inequality holds due to Cauchy-Schwarz inequality. For $I_{1}$, we use Lemma A.1. Notice that the length of $|{\mathcal{T}}|=T-1$ and the definition of ${\epsilon_{\text{pretrain}}}$, we have

$$ $\displaystyle I_{1}\leq({\epsilon_{\text{pretrain}}}/C_{{\mathtt{Dec}}})^{2}.$ (A.3) $$

For $I_{2}$, by the definition of $\chi^{2}$ distance, we have

$$ $\displaystyle I_{2}$ $\displaystyle=\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}}\frac{{ \widehat{\mathbb{P}}}({\mathcal{T}})}{\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}} _{T-1}({\mathcal{T}})}$ $\displaystyle=\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}}\frac{{ \widehat{\mathbb{P}}}({\mathcal{T}})}{{\mathtt{Dec}}_{T-1}({\mathcal{T}}|s)} \cdot\frac{{\mathtt{Dec}}_{T-1}({\mathcal{T}}|s)}{\mathbb{P}^{\mathbf{M},{ \text{Alg}^{C}}}_{T-1}({\mathcal{T}})}$ $\displaystyle\leq C_{{\mathtt{Dec}}}^{2}[1+\chi^{2}({\widehat{\mathbb{P}}}( \cdot),{\mathtt{Dec}}_{T-1}(\cdot|s))].$ (A.4) $$

where the inequality holds due to Assumption 5.3.
Substituting (A.3) and (A.4) into (A.2), and substituting (A.2) into (A.1), we have

$$ $\displaystyle|\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}},a\sim \overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s)}r(s,a)-\mathbb{E}_{{ \mathcal{T}}\sim{\widehat{\mathbb{P}}},a\sim{\text{Alg}_{\widehat{\bm{\theta}} }}(\cdot|{\mathcal{T}},s)}r(s,a)|$ $\displaystyle\leq{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({\widehat{ \mathbb{P}}}(\cdot),{\mathtt{Dec}}_{T-1}(\cdot|s))},$ (A.5) $$

holds for any ${\widehat{\mathbb{P}}}\in\mathcal{P}$. Finally, we have

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}^{s}\sim{\widehat{\mathbb{P}}^{s}}(\cdot |\mathcal{D},s),a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}^{s},s)}r( s,a)$ $\displaystyle\geq\mathbb{E}_{{\mathcal{T}}^{s}\sim{\widehat{\mathbb{P}}^{s}}( \cdot|\mathcal{D},s),a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal {T}}^{s},s)}r(s,a)-{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({\widehat{ \mathbb{P}}^{s}}(\cdot|\mathcal{D},s),{\mathtt{Dec}}_{T-1}({\mathcal{T}}|s))}$ $\displaystyle\geq\mathbb{E}_{{\mathcal{T}}^{s}\sim\mathbb{P}^{*,s}(\cdot| \mathcal{D},s),a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}}^{ s},s)}r(s,a)-{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}(\mathbb{P}^{*,s}( \cdot|\mathcal{D},s),{\mathtt{Dec}}_{T-1}({\mathcal{T}}|s))},$ $\displaystyle\geq\mathbb{E}_{{\mathcal{T}}^{s}\sim\mathbb{P}^{*,s}(\cdot| \mathcal{D},s),a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}^{s},s)}r(s ,a)-2{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}(\mathbb{P}^{*,s}(\cdot| \mathcal{D},s),{\mathtt{Dec}}_{T-1}({\mathcal{T}}|s))},$ $\displaystyle\geq\mathbb{E}_{{\mathcal{T}}^{s}\sim\mathbb{P}^{*,s}(\cdot| \mathcal{D},s),a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}^{s},s)}r(s ,a)-2{\epsilon_{\text{pretrain}}}C_{{\mathtt{Dec}}}\sqrt{1+\chi^{2}(\mathbb{P} ^{*,s}(\cdot|\mathcal{D},s),\mathbb{P}^{\mathbf{M},{\text{Alg}^{C}}}_{T-1}( \cdot))},$ $$

where the first inequality holds due to (A.5), the second one holds due to the selection rule of ${\widehat{\mathbb{P}}^{s}}$, the third one holds due to (A.5) and the last one holds due to Assumption 5.3. This concludes our proof.

∎

###### Lemma A.1 (Lemma 20, Lin et al. 2023 ) .

###### Lemma A.2 .

###### Proof.

###### Proof.

### A.2 Proof of Theorem 5.5

###### Proof.

Suppose we are at step $t$ and we condition on all past history $\mathcal{H}_{t-1}=(s_{1},a_{1},r_{1},\dots,s_{t-1},a_{t-1},r_{t-1})$. Let $\mathbf{M}_{t}$ be the task at $t$ step and $s_{t}$ be the state observed. Then with probability at least $1-1/m_{c}-\delta$, the following event $\mathcal{E}_{t}$ holds:

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}\sim\mathbb{P}^{\mathbf{M}_{t},{\text{ Alg}^{C}}}_{t-1}}\bigg{[}{\text{D}_{\text{H}}}^{2}(\overline{{\text{Alg}^{E}}} (\cdot|{\mathcal{T}}_{t-1},s_{t}),{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{ \mathcal{T}}_{t-1},s_{t}))\bigg{]}$ $\displaystyle\leq m_{c}\bigg{[}c\cdot\frac{T\log(\delta^{-1}\mathcal{N}(1/({n_ {\text{pre}}}T)^{2})T^{2})}{{n_{\text{pre}}}}+T{\epsilon_{\text{real}}}\bigg{]},$ $$

Now following (A.2) in the proof of Theorem 5.4, we still have

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}}|\mathbb{E}_{ a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}},s_{t})}r(s,a)-\mathbb{E}_ {a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}},s_{t})}r(s,a)|$ $\displaystyle\leq\sqrt{\underbrace{\mathbb{E}_{{\mathcal{T}}\sim\mathbb{P}^{ \mathbf{M}_{t},{\text{Alg}^{C}}}_{t-1}}{\text{D}_{\text{H}}}^{2}(\overline{{ \text{Alg}^{E}}}(\cdot|{\mathcal{T}},s_{t}),{\text{Alg}_{\widehat{\bm{\theta}} }}(\cdot|{\mathcal{T}},s_{t}))}_{I_{1}}}\cdot\sqrt{\underbrace{\mathbb{E}_{{ \mathcal{T}}\sim\mathbb{P}^{\mathbf{M}_{t},{\text{Alg}^{C}}}_{t-1}}\bigg{(} \frac{{\widehat{\mathbb{P}}}({\mathcal{T}})}{\mathbb{P}^{\mathbf{M}_{t},{\text {Alg}^{C}}}_{t-1}({\mathcal{T}})}\bigg{)}^{2}}_{I_{2}}}$ (A.6) $$

Then following Lemma A.2, under event $\mathcal{E}_{t}$, we have

$$ $\displaystyle I_{1}\leq({\epsilon_{\text{pretrain}}}/C_{{\mathtt{Dec}}})^{2}, \ {\epsilon_{\text{pretrain}}}/C_{{\mathtt{Dec}}}=T^{2}\cdot\sqrt{c\cdot\frac{ T\log(\mathcal{N}(1/({n_{\text{pre}}}T)^{2})T^{2})}{{n_{\text{pre}}}}+T{ \epsilon_{\text{real}}}}.$ $$

For $I_{2}$, similar to (A.4), we have

$$ $\displaystyle I_{2}\leq C_{{\mathtt{Dec}}}^{2}[1+\chi^{2}({\widehat{\mathbb{P} }}(\cdot),{\mathtt{Dec}}_{t-1}(\cdot|s_{t}))].$ $$

Therefore, we have for any ${\widehat{\mathbb{P}}}$,

$$ $\displaystyle|\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}(\cdot| \mathcal{H}_{t-1},s_{t}),a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}, s_{t})}r(s_{t},a)-\mathbb{E}_{{\mathcal{T}}\sim{\widehat{\mathbb{P}}}(\cdot| \mathcal{H}_{t-1},s_{t}),a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{ \mathcal{T}},s_{t})}r(s_{t},a)|$ $\displaystyle\leq{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({\widehat{ \mathbb{P}}}(\cdot|\mathcal{H}_{t-1},s_{t}),{\mathtt{Dec}}_{t-1}(\cdot|s_{t}))}.$ (A.7) $$

Taking union bound and let $m_{c}=T^{2},\delta=1/T^{2}$, then we get $\mathcal{E}_{1},...,\mathcal{E}_{T}$ hold with probability at least $1-2/T$. Next we bound the suboptimal gap at $t$ step as follows:

$$ $\displaystyle\mathbb{E}_{{\mathcal{T}}^{t-1}\sim{\widehat{\mathbb{P}}^{t}}( \cdot|\mathcal{H}_{t-1},s_{t}),a\sim\overline{{\text{Alg}^{E}}}(\cdot|{ \mathcal{T}}^{t-1},s_{t})}r(s_{t},a)$ $\displaystyle\leq\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}^{t-1}\sim{ \widehat{\mathbb{P}}^{t}}(\cdot|\mathcal{H}_{t-1},s_{t}),\\ a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}}^{t-1},s_{t})\end {subarray}}r(s_{t},a)+{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({\widehat{ \mathbb{P}}^{t}}(\cdot|\mathcal{H}_{t-1},s_{t}),{\mathtt{Dec}}_{t-1}(\cdot|s_{ t}))}$ $\displaystyle\leq\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}^{t-1}\sim{ \mathbb{P}^{*,t}}(\cdot|\mathcal{H}_{t-1},s_{t}),\\ a\sim{\text{Alg}_{\widehat{\bm{\theta}}}}(\cdot|{\mathcal{T}}^{t-1},s_{t})\end {subarray}}r(s_{t},a)+{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({\mathbb{P} ^{*,t}}(\cdot|\mathcal{H}_{t-1},s_{t}),{\mathtt{Dec}}_{t-1}(\cdot|s_{t}))}$ $\displaystyle\leq\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}^{t-1}\sim{ \mathbb{P}^{*,t}}(\cdot|\mathcal{H}_{t-1},s_{t}),\\ a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}^{t-1},s_{t})\end{subarray }}r(s_{t},a)+2{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({\mathbb{P}^{*,t}}( \cdot|\mathcal{H}_{t-1},s_{t}),{\mathtt{Dec}}_{t-1}(\cdot|s_{t}))}$ $\displaystyle\leq\mathbb{E}_{\begin{subarray}{c}{\mathcal{T}}^{t-1}\sim{ \mathbb{P}^{*,t}}(\cdot|\mathcal{H}_{t-1},s_{t}),\\ a\sim\overline{{\text{Alg}^{E}}}(\cdot|{\mathcal{T}}^{t-1},s_{t})\end{subarray }}r(s_{t},a)+2C_{{\mathtt{Dec}}}{\epsilon_{\text{pretrain}}}\sqrt{1+\chi^{2}({ \mathbb{P}^{*,t}}(\cdot|\mathcal{H}_{t-1},s_{t}),\mathbb{P}^{\mathbf{M}_{t},{ \text{Alg}^{C}}}_{t-1}(\cdot))},$ (A.8) $$

where the first inequality holds due to (A.7), the second one holds due to the optimism principle, the third one holds due to (A.7), and the last one holds due to Assumption 5.3. Taking summation of (A.8) from $1$ to $T$ concludes our proof.
∎

###### Proof.

## Appendix B More Experiment Details

In this section, we provide additional details on our experiments in Section 4.1. The tables included below outline the hyperparameter settings that were used throughout the evaluation process.

**Table 5: Hyperparameter settings ($k$ and $c$) for different benchmarks and model sizes.**
| Benchmark | Alfworld | Webshop | HotPotQA |
| --- | --- | --- | --- |
| Llama3.1 8b | $k=5,c=5$ | $k=5,c=0$ | $k=5,c=5$ |
| Llama3.1 70b | $k=5,c=5$ | $k=5,c=0$ | $k=5,c=0$ |

Notably, there are a lot of burgeoning representative benchmarks and tasks across various domains, like reasoning (Zeng et al., ), code generation (Dai et al., ), long context information extraction (Ge et al., ; Wang et al., ), visual recognition (Wang et al., ; Kang et al., ; Yang et al., ; Chen et al., ), math reasoning (Xiong et al., ; Zhao and Zhang, ), classification (Wan, ; Kang et al., ; Huang et al., ; Liu et al., ; Tao et al., ), harm detection (Zhao et al., ; Huang and Sun, ; Fan and Tao, ). These vast domain of applications holds the potential of CoPS. We leave to apply CoPS to above benchmarks to future work.

## Appendix C Prompt Template

Our prompt framework is designed with the considerations of simplicity, efficiency, and generalizability. Moreover, we aim to leverage the high-performing long-context capabilities of modern LLMs (Dubey et al., ) to a maximal degree. In one sentence to describe our prompting philosophy: previous success trajectories are seen by the agent as *experiences* it has gone through in the same trial. As an example from the Alfworld experiment, a in-context demonstration is insert into the prefix of the agent’s prompt as follows:
{mdframed}

[User] Interact with a household to solve a task. Here are a few examples.You are in the middle of a room. Looking quickly around you, you see a cabinet 13, a cabinet 12, a cabinet 11, a cabinet 10, a cabinet 9, a cabinet 8, a cabinet 7, a cabinet 6, a cabinet 5, a cabinet 4, a cabinet 3, a cabinet 2, a cabinet 1, a coffeemachine 1, a countertop 1, a diningtable 1, a drawer 1, a fridge 1, a garbagecan 1, a microwave 1, a shelf 3, a shelf 2, a shelf 1, a sinkbasin 1, a stoveburner 4, a stoveburner 3, a stoveburner 2, a stoveburner 1, and a toaster 1.Your task is to: put a hot apple in fridge.[Assistant] think: To solve the task, I need to find and take an apple, then heat it with microwave, then put it in fridge.[User] OK.[Assistant] think: First I need to find an apple. An apple is more likely to appear in fridge (1), diningtable (1), coffeetable (1), drawer (1), cabinet (1-13), garbagecan (1). I can check one by one, starting with fridge 1.[User] OK.[Assistant] go to fridge 1[User] The fridge 1 is closed.[experience detail omitted][Assistant] go to fridge 1[User] The fridge 1 is open. In it, you see a cup 1, and a egg 1.[Assistant] put apple 1 in/on fridge 1[User] You put the apple 1 in/on the fridge 1.[more in-context experiences][User] Examples finished. Here is the task:You are in the middle of a room. Looking quickly around you, you see a cabinet 6, a cabinet 5, a cabinet 4, a cabinet 3, a cabinet 2, a cabinet 1, a coffeemachine 1, a countertop 3, a countertop 2, a countertop 1, a drawer 3, a drawer 2, a drawer 1, a fridge 1, a garbagecan 1, a microwave 1, a shelf 3, a shelf 2, a shelf 1, a sinkbasin 1, a stoveburner 4, a stoveburner 3, a stoveburner 2, a stoveburner 1, and a toaster 1.Your task is to: put a saltshaker in drawer.[Assistant] think: To solve the task, I need to find and take a saltshaker, then put it in/on a drawer.[real trial begins]

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. What encoders are used for generating embeddings of start states?
2. Have you tried utilizing both start state and resultant actions as input to this embedding model? This would encapsulate a demonstration policy instead of just the start state distribution.
soundness: 3
strengths: Strengths:
1. The paper is well written and easy to understand
2. The theoretical section is clear with well-defined notations used consistently through the manuscript.
summary: The authors propose COPS, a method which utilizes an offline demonstration dataset of “experiences” and study how to use these experiences to solve downstream embodied and question-answering tasks. The authors motivate the work theoretically, drawing parallels to works in distribution selection and retrieval. Subsequently, they demonstrate the performance of COPS on AlfWorld, HotPotQA and WebShop.
weaknesses: Weaknesses:
1. **Differences between COT/Few shot prompting?** The method is very similar to any form of few shot prompting and similar retrieval augmented generation works. The authors utilize an embedding model to calculate similarity between a current starting state and one sampled from the experience dataset. Additionally, their measure function for selecting the distribution to sample experiences from is a combination of reward and the similarity between the current start state and those in the dataset as defined by the embedding model. This to me, feels like a simple extension of RAG style methods with the additional reward label. This is interesting, yet on its own is not novel enough. Especially because none of the necessary offline RL analysis is conducted on this optimization. For instance, does this result in trajectory stitching, i.e., does the actor combine multiple subtrajectories in a demonstration to yield “stitched behaviors”? Can the agent outperform the demonstrations provided in the dataset? 
2. **Unclear what the quality of the demonstration dataset is?:** This brings me to my second point, it’s unclear what the quality of demonstrations utilized is. Do you only have successful trajectories in your demonstration? What if you only used suboptimal demonstrations? No such analysis is conducted. 
3. **Small experimentation setup:** The experiments section currently reads like that of a paper written in 2022 (which in LLM-application research is a significant period). No error bars/multiple seed runs are reported. The analysis is performed on 3 somewhat outdated benchmarks. This should be expanded. Why are some baselines missing for some of the benchmarks? For example, Table 3 does not report RAP performance. LATS is missing in Table 1?
4. Why is the pretraining performance being considered in your analysis? My understanding was that no LLMs had been pretrained for this work.
5. Since this is such an activate area of research, it would good to show how baselines discussed in the related works section actually perform. It is less convincing to read, *“However, their approach demonstrated poor sample efficiency, making it less suited for real-world agent settings where opportunities for trial and error are limited”* instead of seeing a plot with number of samples on the x-axis and success rate on the y-axis for this method.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please refer to the weaknesses section for main questions. More minor questions are given below

- How is the reward r calculated in this work?

- How is distance between experiences are calculated?
soundness: 3
strengths: - The paper is well written and easy to follow
- The paper focuses on an important aspect of using cross-task experience to improve performance in sequential decision making.
summary: The paper proposes a method for utilizing experience from cross-tasks in order to improve performance. The proposed method samples experience from a probability distribution that captures reward and distance between experiences. Results are provided for widely studied ALFWorld, Webshop and HotPotQA environments. Authors also propose a theoretical framework for agents who are utilizing prior experience for performance improvement.
weaknesses: - The paper fails to discuss relevant literature that uses cross-task experience for improving performance. For example O3D paper by Xiao et al. https://openreview.net/pdf?id=bkY8zEDdH9 proposes a method that uses offline trajectories from all tasks to distill knowledge for performance improvement. 

- Authors only provide results on 2 models from Llama family. How well does this method work with SOTA models such from GPT or Claude family

- The main contribution of the paper is proposing a method that benefit from cross-task experience. However, authors fail to illustrate this in given experimental results. What is the contribution of cross-task experiences (compared to same task experience) in the provided performance improvement?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: Q1. Please see the questions in the first weakness above.

Q2. Regarding the second weakness, what is the main difference between CoPS and RAP? And, what makes CoPS to perform better than RAP?
soundness: 2
strengths: S1. It is interesting to propose an idea that selects distribution-matched experiences from a memory bank for improving the performance of LLM agents.

S2. This paper demonstrates that CoPS can achieve higher success rates than recent advancements such as Reflexion, RAP, and LATS on the representative benchmarks such as ALFWorld, WebShop, and HotPotQA.
summary: This paper proposes CoPS (Cross-Task Experience Sharing), a method that can improve LLM agents by sharing distribution-matched experiences stored in a memory bank. CoPS first generates a trial experience from a LLM by conditioning on an initial state. Next, it sets a probability distribution that can approximately maximize the expected total reward while keeping the distribution close to a task-dependent distribution of the LLM. Then, it repeatedly samples candidate experiences from the probability distribution, and uses them as few-shot examples to sample an action from the LLM. This paper evaluates CoPS on three representative benchmarks such as ALFWorld, WebShop, and HotPotQA. The experiment results show that CoPS can achieve higher success rates than recent advancements such as Reflexion, RAP, and LATS on the benchmarks.
weaknesses: W1. This paper aims to share cross-task experiences from a memory bank. However, it is rather unclear how to construct cross-task experiences in the memory bank. More specifically, how is offline data collected? Which LLMs are used as a policy to generate offline data? How many experiences are required to achieve the performance provided in the paper? How much different tasks can be used together to take advantages of cross-task experience sharing?

W2. To enable cross-task experience sharing, this paper proposes to find a probability distribution (in Equation 2.2) that can maximize the expected reward while keeping the distribution close to a task-dependent distribution of a LLM. However, this paper approximates the probability distribution by using cosine similarity between experiences. This approximation seems to make CoPS too similar to RAP.

W3. I am not sure that it is a fair comparison to constraint LAST to have similar running time with CoPS. LAST aims to improve the performance by using inference-time compute.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: Apart from the weakness section, I also have a few questions:

1. How is the task defined? It is a bit unclear to me in the experiments -- does the author use the experience from the same benchmark or from other benchmarks as well?

2. How is the sampled experience number selected? How would the number affect the performance? Note that more sampled experience will result in more context length.
soundness: 3
strengths: - The core idea of leveraging cross-task experiences for LLM agents is novel and potentially impactful. The pessimism-based selection strategy provides a theoretically grounded approach to experience sharing.
 - The implementation is relatively straightforward and generalizable across different environments, requiring minimal task-specific modifications.
 - The empirical results show promising performance improvements, particularly with smaller models like Llama 3.1 8b, suggesting potential resource efficiency benefits.
summary: This paper proposes CoPS (Cross-Task Experience Sharing), an algorithm that aims to enhance LLM-based agents’ sequential reasoning by leveraging experiences across different tasks. The method uses a pessimism-based strategy to select relevant experiences from a memory bank while minimizing distribution shift risks. The authors evaluate CoPS on three benchmarks (Alfworld, Webshop, HotPotQA) and claim superior performance compared to baselines like Reflexion and RAP.
weaknesses: 1. The idea seems similar to the Retrieval-Augmented Generation (RAG) technique. The paper lacks a comparison and discussion with traditional RAG approaches that also leverage external knowledge for LLM enhancement. The pessimism-based selection strategy could be better positioned against existing RAG retrieval methods like hybrid search and recursive retrieval[1].
2. The relationship to LLM agent memory mechanisms is insufficiently explored. For instance, no comparison is made with memory bank approaches that handle both short-term and long-term memory [2,3,4]. The paper should discuss how CoPS differs from or improves upon existing memory management solutions in LLM agents.
3. The current implementation lacks consideration of hybrid memory architectures that combine both short-term and long-term memory components. The system could benefit from incorporating recent advances in memory management like episodic memory modules or hierarchical attention mechanisms. Also, the paper doesn't address how the experience selection strategy could be enhanced with modern RAG techniques like recursive retrieval or adaptive retrieval mechanisms.
4. No ablation studies comparing different memory retrieval strategies (e.g., semantic search vs. keyword-based vs. hybrid approaches). Missing evaluation of memory retention and recall over extended periods, which is crucial for long-term agent deployment. Limited analysis of how the system handles memory updates and forgetting mechanisms compared to other memory-augmented LLM approaches[3].
5. Presentation could be improved. For instance, Fig. 1 does not with adequate explanation and it is hard to understand what does the example task means.

Refs:
[1] Retrieval Augmented Generation (RAG) for LLMs https://www.promptingguide.ai/research/rag

[2] Zhang, Zeyu, et al. "A survey on the memory mechanism of large language model based agents." arXiv preprint arXiv:2404.13501 (2024).

[3] MemoryBank: Enhancing Large Language Models with Long-Term Memory, https://ojs.aaai.org/index.php/AAAI/article/view/29946

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

[5] A Survey on Retrieval-Augmented Text Generation for Large Language Models - NASA ADS https://ui.adsabs.harvard.edu/abs/2024arXiv240410981H/abstract

Meta-review: This paper proposes a RAG-like approach, with multiple tasks. Reviewers generally commented that the work lacked significant novelty compared to the original RAG, while the experiments lacked rigor. There was a healthy discussion which was not sufficient for the reviewers to increase their scores, as concerns remained. The paper therefore fails to meet the bar for acceptance.

Decision: Reject