Efficient Sequential Decision Making with Large Language Models (2024)

Abstract: This paper focuses on extending the success of large language models (LLMs) to sequential decision making. Existing efforts either (i) re-train or finetune LLMs for decision making, or (ii) design prompts for pretrained LLMs. The former approach suffers from the computational burden of gradient updates, and the latter approach does not show promising results. In this paper, we propose a new approach that leverages online model selection algorithms to efficiently incorporate LLMs agents into sequential decision making. Statistically, our approach significantly outperforms both traditional decision making algorithms and vanilla LLM agents. Computationally, our approach avoids the need for expensive gradient updates of LLMs, and throughout the decision making process, it requires only a small number of LLM calls. We conduct extensive experiments to verify the effectiveness of our proposed approach. As an example, on a large-scale Amazon dataset, our approach achieves more than a 6x performance gain over baselines while calling LLMs in only 1.5% of the time steps.

## introduction sequential decision making addresses the problem of adapting an agent to an unknown environment, where the agent learns through a feedback loop by repeatedly receiving contexts, selecting actions, and observing feedback. this approach has been widely applied in real-world scenarios, including recommendation systems @xcite , healthcare @xcite , and dialogue systems @xcite . with the significant success of large language models (llms) in natural language processing @xcite @xcite , an important next step figure 1: performance comparison (higher is better) on the amazoncat-13k dataset. the decision making task is to predict item tags based on textual descriptions. we compare three approaches: (i) a standard decision making algorithm, (ii) a pretrained llm as decision making agent, and (iii) our approach that balances the above two methods. we defer further details to section 4. in this paper, we propose a new approach to efficiently incorporate large pretrained models into sequential decision making environments, without the need for expensive model re-training or finetuning. we run experiments (see fig. 1 and its caption for settings) on the amazoncat-13k dataset @xcite and observe that: to take advantage of both methods, we adapt online model selection algorithms @xcite @xcite to a framework that can automatically balance the performance of llm-powered policies/agents and standard decision making algorithms. initially, the framework relies more on llm-powered policies to achieve good initial results. as standard decision making algorithms begin to adapt to the environments, it gradually shifts towards these algorithms. to our knowledge, this work presents the first result in leveraging online model selection algorithms to efficiently incorporate llms into sequential decision making. our framework also offers several compelling advantages: ## problem setting we focus on contextual bandits, a key problem in sequential decision making that emphasizes the fundamental challenge of balancing exploration and exploitation @xcite . in contextual bandits, a learner interacts with an unknown environment over @xmath0. at each round @xmath1, the learner receives a context x @xmath2, selects an action a @xmath3, and then observes a bounded loss ℓ t (a t ) (sampled from an unknown distribution), where ℓ t : @xmath4, 1] is the underlying loss function. contextual bandits can be viewed as the simplest form of reinforcement learning where state transitions are abstracted away. following the convention @xcite @xcite , we assume that the learner has access to a function class f ⊆ (x × @xmath5, 1]) to approximate an unknown true loss function let π ⋆ (x) = arg min a f ⋆ (x, a) denote the optimal policy with respect to the true expected loss (i.e., always selecting an action that achieves the smallest expected loss). the learner's goal is to choose a policy π = (π 1 , • • • , π t ) to minimize the cumulative regret, which is defined as reg(t ) := we focus on the setting where the context space and the action space are subspaces of the language space, i.e., the learner interacts with an environment through textual contexts and actions, and actions that induce low loses are usually consistent with commonsense knowledge and/or reasoning. 1 therefore, our setting motivates leveraging pretrained large language models (llms) into contextual bandits. specifically, we consider a pretrained llm: prompt @xmath6, that maps a prompt p to a textual response o @xcite @xcite . since llms are pretrained to acquire general knowledge about the world, we expect the output o t ∼ llm(@xmath7, when prompting llms with the context x t (and other relevant information), would provide informative guide for the decision making process. additional notation. for an integer @xmath8, we let [n] denote the set {1, . . . , n}. for a finite set z, we let unif(z) denote the uniform distribution over all the elements in z. we use e @xmath9, i.e., its i-th entry is 1 and the rest entries are 0. ## methods we present our approach for efficiently incorporating llms into contextual bandits/decision making in this section. we provide the algorithmic foundation in section 3.1 and various sampling strategies in section 3.2. ## empirical results we conduct extensive experiments to examine the effectiveness of our proposed framework. we present experimental setups in section 4.1, our main results in section 4.2, and ablation study in section 4.3. we defer additional experimental details to appendix a. code to reproduce all results is available at https://github.com/dchen48/ dmwithllm . ## analyses llms empower contextual bandit algorithms. as shown in fig. 2 , algorithm 2 consistently outperforms its base algorithms. since the llm backbones in llm-powered policies are never updated (for efficiency reasons), we hypothesizes that our algorithm 2 empowers its bandit base algorithms with the help of llms. to test this hypothesis, we first plot the real-time probability p cb t of algorithm 2 sampling its contextual bandit base algorithm (fig. 4 , left). since p cb t quickly increases its value to (around) 1 after the initial learning stage, we know that the contextual bandit base algorithm within algorithm 2 plays an important role after the initial stage. we then plot the hypothetical performance of the contextual bandit base algorithm within algorithm 2 (as if it were played at every time step). as shown in fig. 4 (right), the contextual bandit base algorithm within algorithm 2 (solid black line) achieves much better performance compared to the stand-alone contextual bandit algorithm (0.17546 vs. 0.11773). since the main difference lies in the incorporation of data selected by llm-powered policy, this shows that llm selected data helps contextual bandit algorithm learn better. we also draw the hypothetical performance of spannergreedy learned with purely llm selected data (solid purple line in fig. 4 right), which is worse than spannergreedy (0.06669 vs. 0.11773). this suggests that exploration in contextual bandit algorithm is also important and cannot be replaced with llm selected data. algorithm 2 with multiple llms. we run algorithm 2 with two llms: flan-t5 large and flan-t5 small. we compare this approach to algorithm 2 with either flan-t5 large or flan-t5 small. we use n s and n l to denote the number of flan-t5 large and flan-t5 small calls, respectively, and show the results in llms for decision making. while there have been many studies that leverage llms into supervised learning @xcite @xcite , the understanding of how to leverage llms into sequential decision making is less developed. there exist two main approaches: (i) view decision making as sequence modeling and pretrain/finetune large models to adapt them to unknown environments @xcite @xcite @xcite , and (ii) leverage prompt engineering and in-context learn-ing to adapt pretrained large models to sequential decision making problems @xcite . in this paper, we propose a new approach that efficiently incorporates llms into sequential decision making, addressing drawbacks of previous approaches. ## conclusion in this paper, we study the problem of how to efficiently incorporate large language models into contextual bandits, a key problem in sequential decision making that emphasizes the fundamental challenge of balancing exploration and exploitation. we propose to use online model selection algorithms to adaptively balance llms agents and standard contextual bandit algorithms. statistically, our approach greatly outperforms stand-lone llmpowered policies and contextual bandit algorithms. computationally, our approach avoids the need for expensive re-training or finetuning, and utilizes only a small fraction of llm calls throughout the decision making process. our framework is highly flexible, allowing for the integration of various offthe-shelf pretrained llms. in our experiments, it delivers promising results even when using a language model with only 80 million parameters. 9 8 limitations our current approach primarily addresses contextual bandit problems, a specific case of reinforcement learning that lacks state transitions. although it is possible to abstract away state transitions, treating an episode of reinforcement learning as a single step in a contextual bandit and applying our algorithms, we believe that more fine-grained treatments are necessary to achieve better performance in reinforcement learning. moving forward, we plan to extend our algorithms and analyses to general reinforcement learning problems.