# From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven
Autonomous Systems

Jianliang He Siyu Chen11footnotemark: 1 Fengzhuo Zhang Zhuoran
Yang33footnotemark: 3 Equal contribution.Fudan University. Email:
<EMAIL_ADDRESS>University. Email:
<EMAIL_ADDRESS>University of Singapore.
Email<EMAIL_ADDRESS>
###### Abstract

In this work, from a theoretical lens, we aim to understand why large language
model (LLM) empowered agents are able to solve decision-making problems in the
physical world. To this end, consider a hierarchical reinforcement learning
(RL) model where the LLM Planner and the Actor perform high-level task
planning and low-level execution, respectively. Under this model, the LLM
Planner navigates a partially observable Markov decision process (POMDP) by
iteratively generating language-based subgoals via prompting. Under proper
assumptions on the pretraining data, we prove that the pretrained LLM Planner
effectively performs Bayesian aggregated imitation learning (BAIL) through in-
context learning. Additionally, we highlight the necessity for exploration
beyond the subgoals derived from BAIL by proving that naively executing the
subgoals returned by LLM leads to a linear regret. As a remedy, we introduce
an $\epsilon$-greedy exploration strategy to BAIL, which is proven to incur
sublinear regret when the pretraining error is small. Finally, we extend our
theoretical framework to include scenarios where the LLM Planner serves as a
world model for inferring the transition model of the environment and to
multi-agent settings, enabling coordination among multiple Actors.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries and Related Works
  3. 3 Theoretical Framework for LLM Agents
    1. 3.1 Planner-Actor-Reporter System
    2. 3.2 Performance Metric and Pretraining
  4. 4 LLM Planning via Bayesian Aggregated Imitation Learning
    1. 4.1 Bayesian Aggregated Imitation Learning
    2. 4.2 LLM-Empowered Planning Algorithm
  5. 5 Performance under Practical Setting
    1. 5.1 Pretraining Large Language Model
    2. 5.2 Pretraining Observation-to-Language Translator
    3. 5.3 Performance with Pretrained PAR System
  6. 6 Conclusion
  7. A Additional Background
    1. A.1 Hierarchical Markov Decision Process
    2. A.2 LLM Pretraining under Transformer Architecture
  8. B Extentions
    1. B.1 LLM Planning via Bayesian Aggregated World Model
    2. B.2 LLM-Empowered Multi-Agent Collaboration
  9. C Proof for Section 4: Perfect Setting
    1. C.1 Proof of Proposition 4.2
    2. C.2 Proof of Theorem 4.6
    3. C.3 Proof of Lemma C.1
    4. C.4 Proof of Proposition 4.3
  10. D Proof for Section 5: Practical Setting
    1. D.1 Proof of Theorem 5.5
    2. D.2 Proof of Theorem 5.7
    3. D.3 Proof of Lemma D.1
    4. D.4 Proof of Lemma D.2
  11. E Proof for Section B: Extentions
    1. E.1 Proof of Proposition B.1
    2. E.2 Proof of Corollary B.3
    3. E.3 Proof of Corollary B.4
  12. F Technical Lemmas

##  1 Introduction

The advent of large language models (LLMs) such as GPT-4 (OpenAI,, 2023) and
Llama 2 (Touvron et al.,, 2023) has marked a significant leap in artificial
intelligence, thanks to their striking capabilities in understanding language
and performing complex reasoning tasks. These capabilities of LLMs have led to
the emergence of LLM-empowered agents (LLM Agents), where LLMs are used in
conjunction with tools or actuators to solve decision-making problems in the
physical world. LLM Agents have showcased promising empirical successes in a
wide range of applications, including autonomous driving (Wang et al., 2023b,
; Fu et al.,, 2024), robotics (Brohan et al.,, 2023; Li et al., 2023a, ), and
personal assistance (Liu et al.,, 2023; Nottingham et al.,, 2023). This
progress signifies a crucial advancement in the creation of intelligent
decision-making systems, distinguished by a high degree of autonomy and
seamless human-AI collaboration.

LLMs only take natural languages as input. To bridge the language and physical
domain, LLM-agents typically incorporate three critical components: an LLM
Planner, a physical Actor, and a multimodal Reporter, functioning respectively
as the brain, hands, and eyes of the LLM-agent, respectively. Specifically,
upon receiving a task described by a human user, the LLM Planner breaks down
the overall task into a series of subgoals. Subsequently, the Actor implements
each subgoal in the physical world through a sequence of actions. Meanwhile,
the Reporter monitors changes in the physical world and conveys this
information back to the LLM Planner in natural language form. This dynamic
interaction among Planner, Actor, and Reporter empowers LLM Agents to
understand the environment, formulate informed decisions, and execute actions
effectively, thus seamlessly integrating high-level linguistic subgoals with
low-level physical task execution.

The revolutionary approach of LLM Agents represents a paradigm shift away from
traditional learning-based decision-making systems. Unlike these conventional
systems, LLM Agents are not tailored to any specific task. Instead, they rely
on the synergy of their three distinct components—each trained separately and
often for different objectives. In particular, the LLM Planner is trained to
predict the next token in a sequence on vast document data. Moreover, when
deployed to solve a task, the way to interact with the LLM Planner is via
prompting with the LLM fixed. The Actor, as language-conditioned policies, can
be trained by RL or imitation learning. Moreover, the Reporter, as a
multimodal model, is trained to translate the physical states (e.g., images)
into natural language. This unique configuration prompts critical research
questions regarding the theoretical underpinnings of LLM Agents, particularly
concerning their decision-making effectiveness.

Figure 1: Overview of the Planner-Actor-Reporter (PAR) system as LLM Agents.
Acting as a central controller, the Planner conducts the high-level planning
by storing the history and reasoning through the iterative use of the ICL
ability of LLMs, coupled with explorations. The Actor handles low-level
planning and executes subgoals using pre-programmed skill sets, and the
Reporter perceives and processes multimodal information from environment to
reinforce the ongoing planning.

In this work, we make an initial step toward developing a theoretical
framework for understanding the dynamics and effectiveness of LLM Agents.
Specifically, we aim to answer the following questions: (a) What is a
theoretical model for understanding the performance of LLM Agents? (b) How do
pretrained LLMs solve decision-making problems in the physical world via
prompting? (c) How does an LLM Agent address the exploration-exploitation
tradeoff? (d) How do the statistical errors of the pretrained LLM and Reporter
affect the overall performance of the LLM Agent?

To address Question (a), we propose analyzing LLM Agents within a hierarchical
reinforcement learning framework (Barto and Mahadevan,, 2003; Pateria et al.,,
2021), positioning the LLM Planner and the Actor as policies operating within
high-level POMDPs and low-level MDPs, respectively (§3.1). Both levels share
the same state space—namely, the physical state—though the LLM Planner does
not directly observe this state but instead receives a language-based
description from the Reporter, effectively navigating a POMDP. The action
space of the high-level POMDP is the set of language subgoals. Meanwhile, the
state transition kernel is determined by the pretrained Actor, and thus is
associated with a variable $z$ that summarizes its dependency on low-level
Actor. Such variable is unknown to LLM Planner. After pretraining, without
prior knowledge of the Actor’s quality or the physical environment, the LLM
Planner attempts to solve the high-level POMDP by iteratively generating a
sequence of subgoals based on feedback from the Reporter via prompting. Under
this framework, the overall performance of the LLM Agent can be captured by
the regret in terms of finding the optimal policy of the hierarchical RL
problem in the online setting (§3.2).

Furthermore, to answer Question (b), we prove that when the pretraining data
includes a mixture of expert trajectories, during the prompting stage, the
pretrained LLM Planner essentially performs Bayesian aggregated imitation
learning (BAIL) through in-context learning (Theorem 4.2). This process
involves constructing a posterior distribution over the hidden parameter $z$of
the transition kernel, followed by generating subgoals that emulate a randomly
selected expert policy, weighted according to this posterior distribution.
Such a Bayesian learning mechanism is encoded by the LLM architecture and is
achieved through prompting.

However, since the LLM has no prior knowledge of the physical environment, it
needs to guide the Actor to explore the physical environment. We prove that
merely adhering to BAIL-derived subgoals can lead to the inadequate
exploration, resulting in a linear regret (Proposition 4.3). To mitigate this,
i.e., Question (c), we introduce an $\epsilon$-greedy exploration strategy,
which occasionally deviates from BAIL subgoals in favor of exploration,
significantly enhancing learning efficacy by ensuring a sublinear regret
(Theorem 4.6). Specifically, to address Question (d) we establish that the
regret is bounded by a sum of two terms (Theorem 5.7): a $\sqrt{T}$-regret
related to the number of episodes the LLM Agent is deployed to the
hierarchical RL problem, and an additional term representing the statistical
error from pretraining the LLM Planner and Reporter via maximum likelihood
estimation (MLE) and contrastive learning, respectively (Theorem 2, 5.5).

Finally, we extend our analysis to scenarios where the Planner utilizes the
LLM as world model for inferring the upper-level POMDP’s transition model via
Bayesian model aggregation (Proposition B.1, Corollary B.3). Our theoretical
framework also accommodates a multi-agent context, where the LLM Planner
coordinates with a collaborative team of low-level actors (Corollary B.4).

##  2 Preliminaries and Related Works

#### Large Language Models.

The Large Language Models (LLMs) such as ChatGPT (Brown et al.,, 2020), GPT-4
(OpenAI,, 2023), Llama (Touvron et al.,, 2023), and Gemini (Team et al.,,
2023), are pretrained on vast text corpora to predict in an _autoregressive_
manner. Starting from an initial token
$\ell_{1}\in\mathfrak{L}\subseteq\mathbb{R}^{d}$, where $d$ denotes the
dimension of token vector and $\mathfrak{L}$ denotes the language space, the
LLM, with parameters $\theta\in\Theta$, predicts the next token with
$\ell_{t+1}\sim\mathtt{LLM}_{\theta}(\cdot\hskip 1.42262pt|\hskip
1.42262ptS_{t})$, where $S_{t}=(\ell_{1},\dots,\ell_{t})$ and
$t\in\mathbb{N}$. Each token $\ell_{t}\in\mathfrak{L}$ specifies a word or
word’s position, and the token sequence $S_{t}$ resides in the space of token
sequences $\mathfrak{L}^{*}$. Such an autoregressive generating process
terminates when the stop sequence token is generated.

#### In-Context Learning.

LLMs haved exhibited robust reasoning capabilities and a crucial aspect of
their reasoning prowess is the in-context learning (ICL) ability. This ability
is further enhanced through additional training stages (Iyer et al.,, 2022),
careful selection and arrangement of informative demonstrations (Liu et al.,,
2021; Kim et al.,, 2022), explicit instruction (Honovich et al.,, 2022), and
use of prompts to stimulate chain of thoughts (Wei et al., 2022b, ). Unlike
fine-tuned models customized for specific tasks, LLMs showcase comparable
capabilities by learning from the informative _prompts_ (Li et al.,, 2022; Liu
et al., 2022b, ). Assume that prompt, denoted by
$\mathtt{pt}_{t}=(\ell_{1},\dots,\ell_{t})\in\mathfrak{L}^{*}$, is generated
based on a latent variable $z\in\mathcal{Z}$ autoregressively. The token
follows a generating distribution such that
$\ell_{t}\sim\mathbb{P}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{t-1},z)$ and
$\mathtt{pt}_{t}=(\mathtt{pt}_{t-1},\ell_{t})$, where $\mathcal{Z}$ denotes
the space of hidden information or concepts. The latent structure is commonly
employed in language models, including topic models like LDA (Blei et al.,,
2003), BERT (Devlin et al.,, 2018), generative models like VAE (Kusner et
al.,, 2017), T5 (Raffel et al.,, 2020), and is also widely adopted in the
theoretical analysis of ICL (Xie et al.,, 2021; Zhang et al.,, 2023).
Theoretical understanding of ICL is an active area of research. Since real-
world datasets used for LLM pretraining are difficult to model theoretically
and are very large, ICL has also been studied in stylized setups (Xie et al.,,
2021; Garg et al.,, 2022; Chan et al.,, 2022; Hahn and Goyal,, 2023; Zhang et
al.,, 2023). In this paper, we build upon the framework attributing the ICL
capability to Bayesian inference (Xie et al.,, 2021; Jiang,, 2023; Zhang et
al.,, 2023), which posits that the pretrained LLMs predict the next token with
probability by aggregating the generating distribution concerning latent
variable $z\in\mathcal{Z}$ over the posterior distribution. Moreover, a series
of practical experiments, including Wang et al., 2023a ; Ahuja et al., (2023),
provide empirical support for this Bayesian statement.

#### LLM Agents.

LLMs, as highlighted in OpenAI, (2023), are powerful tools for the task
planning (Wei et al., 2022a, ; Hu and Shu,, 2023). The success of LLM agent
marks a shift from task-specific policies to a pretrain-finetune-prompt
paradigm. By breaking down the complex tasks into subgoals, LLM Agent
facilitates the effective zero-shot resource allocation across environments.
For instance, envision a scenario where a robotic arm is tasked with “ _move a
teapot from the stove to a shelf_ ”, a task for which the robotic arm may not
be pretrained. However, leveraging LLMs allows the decomposition of the task
into a sequence of executable subgoals: “ _grasp the teapot_ ”, “ _lift the
teapot_ ”, “ _move the teapot to the shelf_ ”, and “ _release the teapot_ ”.

In the conventional task-planning and decision-making problems, symbolic
planners have commonly been employed to transform them into search problems
(Bonet and Geffner,, 2001; Ghallab et al.,, 2004) or to design distinct
reinforcement learning or control policies for each specific scenario. Recent
empirical studies have shifted towards leveraging LLMs as symbolic planners in
various domains, including robotic control (Mandi et al.,, 2023; Brohan et
al.,, 2023; Li et al., 2023a, ; Du et al.,, 2023), autonomous driving (Wang et
al., 2023b, ; Fu et al.,, 2024) and personal decision assistance (Li et al.,,
2022; Lin et al., 2023a, ; Hu et al.,, 2023; Liu et al.,, 2023; Nottingham et
al.,, 2023). Another recent line of research has been dedicated to devising
diverse prompting schemes to enhance the reasoning capability of LLMs (Wei et
al., 2022b, ; Yao et al., 2023a, ; Yao et al., 2023b, ; Hao et al.,, 2023).
Despite the considerable empirical success, there is a lack of comprehensive
theoretical analysis on LLM Agent. In this paper, we formalize this approach
into a hierarchical LLM-empowered planning framework and provide a theoretical
analysis of its performance. Two recent works by Liu et al., (2023) and Lee et
al., (2023) also aim to establish provable algorithms for planning with LLMs
or decision-pretrained Transformers (DPT). In comparison, we discuss both the
plausibility of taking LLMs as a subgoal generator (Lee et al.,, 2023) and
simulated world model (Liu et al.,, 2023). Furthermore, we provide a
statistical guarantee for pretrained models and conduct a detailed examination
of the algorithm’s performance in practical settings, bringing our analysis
closer to real-world applications.

##  3 Theoretical Framework for LLM Agents

To formalize the architecture of LLM Agents, we propose a general theoretical
framework—Planner-Actor-Reporter (PAR) system. Furthermore, the problem is
modeled as a hierarchical RL problem (Pateria et al.,, 2021). Specifically,
the Planner, empowered by LLMs, conducts high-level task planning within the
language space; the Actor, pretrained before deployment, undertakes low-level
motion planning within the physical world; and the Reporter, equipped with a
sensor to sense the physical environment, processes the information and feeds
it back to the Planner, bridging the gap between language space and the
physical world (see §3.1). Additionally, we present the performance metric and
pretraining methods of LLMs for the Planner and translators for the Reporter
in §3.2.

###  3.1 Planner-Actor-Reporter System

In this section, we delve into details of the PAR system under Hierarchical
Markov Decision Process (HMDP). At the high level, the Planner empowered by
LLM handles task planning by decomposing tasks into subgoals to solve a
language-conditioned Partially Observable Markov Decision Process (POMDP) with
a finite horizon $H$. At the low level, the Actor translates these subgoals
into the actionable steps in the physical world to handle a language-
conditioned Markov Decision Process (MDP) with a finite horizon
$H_{a}$111Throughout the paper, we use the notation $\bar{\cdot}$ to
distinguish low-level elements from their high-level counterparts.. Please
refer to the right panel of Figure 1 for a detailed example of LLM Agent, and
see Figure 2 for an overview of the hierarchical interactive process.

#### Low-level MDP.

Let $\mathcal{G}\subseteq\mathfrak{L}$ be the space of language subgoals,
${\mathcal{S}}$ and $\mathcal{A}$ respectively denote the space of physical
states and actions. At high-level step $h$, the low-level MDP is specified by
a transition kernel
$\mathbb{T}_{h}=\\{\mathbb{T}_{h,\bar{h}}\\}_{\bar{h}\in[H_{a}]}$ and the
rewards that depends on subgoal $g\in\mathcal{G}$. Following this, the Actor
is modelled as a language-conditioned policy
$\mu=\\{\mu_{g}\\}_{g\in\mathcal{G}}$, where
$\mu_{g}=\\{\mu_{\bar{h}}(\cdot|\cdot,g)\\}_{\bar{h}\in[H_{a}]}$ and
$\mu_{\bar{h}}:{\mathcal{S}}\times\mathcal{G}\mapsto\Delta(\mathcal{A})$.
Assume that the Actor stops at step $H_{a}+1$, regardless of the subgoal
achievement. Subsequently, the Planner receives the observation of the current
state $\bar{s}_{h,H_{a}+1}$ from the Reporter, and sends a new subgoal to the
Actor based on the historical feedback.

#### High-level POMDP.

Suppose that a low-level episode corresponds to a single high-level action of
the Planner. Thus, the high-level POMDP reuses the physical state space
${\mathcal{S}}$ as the state space, but takes the subgoal space $\mathcal{G}$
as the action space instead. Following this, the high-level transition kernel
is jointly determined by the low-level policy $\mu$ and the physical
transition kernel $\mathbb{T}$ such that

$\displaystyle\mathbb{P}_{z,h}(s^{\prime}\hskip 1.42262pt|\hskip
1.42262pts,g)=\mathbb{P}\big{(}\bar{s}_{h,H_{a}+1}=s^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\bar{s}_{h,1}=s,a_{h,1:\bar{h}}\sim\mu_{g},\bar{s}_{h,2:\bar{h}+1}\sim\mathbb{T}_{h}\big{)},$
(3.1)

where we write $z=(\mathbb{T},\mu)$. Since the LLM-empowered Planner cannot
directly process the physical states, it relies on some (partial) observations
generated by the Reporter. Specifically, let $o_{h}\in\mathcal{O}$ describe
the physical state $s_{h}\in{\mathcal{S}}$ in language through a translation
distribution $\mathbb{O}:\mathcal{O}\mapsto\Delta({\mathcal{S}})$, where
$\mathcal{O}\subseteq\mathfrak{L}$ denotes the space of observations. At each
step $h\in[H]$, a reward $r_{h}(o_{h},\omega)\in[0,1]$ is obtained, which
depends on both the observation and the task $\omega\in\Omega$ assigned by
human users. Here, $\Omega\subseteq\mathfrak{L}$ denotes the space of
potential tasks in language.

#### Interactive Protocol.

The Planner aims to determine a sequence of subgoal $\\{g_{h}\\}_{h\in[H]}$
such that when the Actor is equipped with policy
$\pi=\\{\pi_{h}\\}_{h\in[H]}$, these subgoals maximize the expected sum of
rewards. During task planning, the Planner must infer both Actor’s intention,
i.e., policy $\mu$, and the environment, i.e., physical transition kernel
$\mathbb{T}$, from the historical information. Thus, $z$ constitutes all the
latent information to the high-level Planner, and denote $\mathcal{Z}$ as the
space of all potential latent variables with $|\mathcal{Z}|<\infty$.

Figure 2: Illustration of structure of HMDP. The low-level MDP is featured by
transition kernel $\mathbb{T}$, which characterizes the dynamics of the
physical environment. The high-level transition is a result of a sequence of
low-level actions in the physical environment, guided by policies
$\mu=\\{\mu_{g}\\}_{g\in\mathcal{G}}$. Thus, high-level POMDP incorporates
latent information $z=(\mathbb{T},\mu)$ originated from the low-level.

To summarize, the interactive protocol is as below: at the beginning of each
episode $t$, Planner receives a task $\omega_{t}$. At step $h$, each module
follows:

#### Module 1: Planner.

After collecting $o_{h}^{t}$ from Reporter, the Planner leverages LLMs for
recommendations on task decomposition, and the policy is denoted by
$\pi^{t}_{h,\mathtt{LLM}}:{\mathcal{T}}^{*}\times(\mathcal{O}\times\mathcal{G})^{h-1}\times\mathcal{O}\times\Omega\mapsto\Delta(\mathcal{G})$,
where ${\mathcal{T}}^{*}$ represents the space of the trajectory sequence with
arbitrary length. LLM’s recommendation is obtained by invoking the ICL ability
with the history-dependent prompt:

$\mathtt{pt}_{h}^{t}=\mathcal{H}_{t}\cup\left\\{\omega^{t},\tau_{h}^{t}\right\\},\quad\mathcal{H}_{t}=\bigcup_{i=1}^{t-1}\left\\{\omega^{i},\tau_{H}^{i}\right\\},$
(3.2)

where $\mathcal{H}_{t}\in{\mathcal{T}}^{*}$ denotes the historical context and
$\tau_{h}^{t}=\\{o_{1}^{t},g_{1}^{t},\dots,o_{h}^{t}\\}$ is the trajectory
until $h$-th step. In the PAR system, Planner retains autonomy and is not
obligated to follow LLM’s recommendations. Let $\pi^{t}_{h}$ be the Planner’s
policy, which partially leverages the LLM’s recommendation
$\pi^{t}_{h,\mathtt{LLM}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})=\mathtt{LLM}_{\theta}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})$. The Planner selects
$g_{h}^{t}\sim\pi_{h}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})$, and sends it to the Actor.

#### Module 2: Actor.

Upon receiving $g_{h}^{t}$ from Planner, the Actor plans to implement
$g_{h}^{t}$ in physical world with pretrained skill sets, denoted by a
subgoal-conditioned policy $\mu=\\{\mu_{g}\\}_{g\in\mathcal{G}}$. A sequence
of actions $\\{a_{h,\bar{h}}\\}_{\bar{h}\in[H_{a}]}$ is executed, where the
dynamics follows $a_{h,\bar{h}}\sim\mu_{\bar{h}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\bar{s}_{h,\bar{h}},g_{h}^{t})$ and
$\bar{s}_{h,\bar{h}+1}\sim\mathbb{T}_{h,\bar{h}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\bar{s}_{h,\bar{h}},a_{h,\bar{h}})$ starting from
$\bar{s}_{h,1}=s_{h}^{t}$. The low-level episode concludes at
$s_{h+1}^{t}=\bar{s}_{h,H_{a}+1}$.

#### Module 3: Reporter.

After the low-level episode concludes, the Reporter collects and reports the
current state $s_{h}^{t}$ via observation $o^{t}_{h+1}$ generated from
$\mathbb{O}_{\gamma}(\cdot\hskip 1.42262pt|\hskip 1.42262pts^{t}_{h+1})$,
where $\mathbb{O}_{\gamma}:\mathcal{S}\mapsto\Delta(\mathcal{O})$ denotes the
distribution of the pretrained translator. Subsequently, the observation
$o_{h+1}^{t}$ of the current state is sent back to the Planner, reinforcing to
the ongoing task planning.

The strength of the PAR system lies in its resemblance to RL (Sutton and
Barto,, 2018), allowing the Planner to iteratively adjust its planning
strategy based on feedback from the Reporter. Moreover, the Reporter empowers
the system to process the real-time information and the integration of
multiple modalities of raw data like RGB, images, LiDAR, audio, and text (Li
et al., 2023b, ; Xu et al.,, 2023). The Actor’s skill sets can effectively be
pretrained using the goal-conditioned RL (Chane-Sane et al.,, 2021; Liu et
al., 2022a, ), language-to-environment grounding (Brohan et al.,, 2023; Huang
et al.,, 2022) or pre-programmed manually (Singh et al.,, 2023).

###  3.2 Performance Metric and Pretraining

#### Performance Metric.

In this paper, we focus on the _performance of the high-level Planner_ , and
regard the low-level Actor as an autonomous agent that can use the pretrained
skill sets following a fixed policy. For any latent variable $z\in\mathcal{Z}$
and policy $\pi=\\{\pi_{h}\\}_{h\in[H]}$ with
$\pi_{h}:(\mathcal{O}\times\mathcal{G})^{h-1}\times\mathcal{O}\times\Omega\mapsto\Delta(\mathcal{G})$,
the value function is defined as

$\mathcal{J}_{z}(\pi,\omega):=\mathbb{E}_{\pi}\left[\sum_{h=1}^{H}r_{h}\left(o_{h},\omega\right)\right],$
(3.3)

where the expectation is taken concerning the initial state $s_{1}\sim\rho$,
policy $\pi$, ground-truth translation distribution $\mathbb{O}$, and
transition kernel $\mathbb{P}_{z}$. For all
$(z,\omega)\in\mathcal{Z}\times\Omega$, there exists an optimal policy
$\pi_{z}^{*}\left(\omega\right)={\rm
argmax}_{\pi\in\Pi}\mathcal{J}_{z}(\pi,\omega)$, where
$\Pi=\\{\pi=\\{\pi_{h}\\}_{h\in[H]},\pi_{h}:(\mathcal{O}\times\mathcal{G})^{h-1}\times\mathcal{O}\times\Omega\mapsto\Delta(\mathcal{G})\\}$.

To characterize the performance under practical setting, we denote
$\mathcal{\widehat{J}}_{z}(\pi,\omega)$ as the value function concerning the
pretrained translator $\mathbb{O}_{\widehat{\gamma}}$, and for all
$\omega\in\Omega$, let $\widehat{\pi}_{z}^{*}\left(\omega\right)={\rm
argmax}_{\pi\in\Pi}\ \widehat{\mathcal{J}}_{z}(\pi,\omega)$ be the optimal
policy in practice. Then, the regret under practical setting is defined as

${\rm
Reg}_{z}(T):=\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{z}(\widehat{\pi}^{t},\omega^{t})\right],$
(3.4)

where $\\{\widehat{\pi}^{t}\\}_{t\in[T]}$ represents the Planner’s policy
empowered by a pretrained $\mathtt{LLM}_{\widehat{\theta}}$ and the
expectation is taken with respect to the context $\mathcal{H}_{t}$ defined in
(3.2) generated by taking $\\{\widehat{\pi}^{i}\\}_{i<t}$ sequentially. Here,
we focus on the performance when the Planner collaborates with a pretrained
PAR system in an environment characterized by $z$ and pretrained Reporter. Our
goal is to design a sample-efficient algorithm that achieves a sublinear
regret, i.e., ${\rm Reg}_{z}(T)=o(T)$.

#### Pretraining Dataset Collection.

The pretraining dataset consists of $N_{\rm p}$ independent samples with
$T_{\rm p}$ episodes such that $\mathcal{D}=\\{D_{n}\\}_{n\in[N_{\rm p}]}$,
where
$D_{n}=\\{z\\}\cup\\{\omega^{t},\tau_{H}^{t},g_{1:H}^{t,*},s_{1:H}^{t}\\}_{t\in[T_{\rm
p}]}$. For each sample, $z\sim\mathcal{P}_{\mathcal{Z}}$ specifies a low-level
MDP with language-conditioned policies and
$\omega^{t}{\sim}\mathcal{P}_{\Omega}$ specifies the sequence of high-level
tasks. Here, $\mathcal{P}_{\mathcal{Z}}$ and $\mathcal{P}_{\Omega}$ denote the
prior distributions. We assume that the joint distribution of each data point
$D$ in the dataset, denoted by $\mathbb{P}_{\mathcal{D}}$, follows that:

$\displaystyle\mathbb{P}_{\mathcal{D}}(D)$
$\displaystyle=\mathcal{P}_{\mathcal{Z}}(z)\cdot\prod_{t=1}^{T_{\rm
p}}\mathcal{P}_{\Omega}(\omega^{t})\cdot\prod_{h=1}^{H}\pi^{*}_{z,h}(g_{h}^{t,*}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h}^{t},\omega^{t})$
$\displaystyle\quad\cdot\mathbb{O}(o_{h}^{t}\hskip 1.42262pt|\hskip
1.42262pts_{h}^{t})\cdot\pi^{b}_{h}(g_{h}^{t}\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})\cdot\mathbb{P}_{z,h}(s_{h+1}^{t}\hskip
1.42262pt|\hskip 1.42262pts_{h}^{t},g_{h}^{t}),$ (3.5)

where $\pi^{b}=\\{\pi^{b}_{h}\\}_{h\in[H]}$ is the behavior policy that
features how the contextual information is collected, and additionally the
label, i.e., optimal subgoal, is sampled from the optimal policy $\pi^{*}_{z}$
by experts. Subsequently, the latent information $z$ is hidden from the
context.

#### LLM Pretraining.

To pretrain LLMs, we adopt a supervised learning approach concerning the
transformer structure, aligning with the celebrated LLMs such as BERT and GPT
(Devlin et al.,, 2018; Brown et al.,, 2020). Specifically, the pretraining
data is constructed based on $\mathcal{D}$. For clarity, we extract the
language data without expert knowledge and write the collected data into a
sequence of ordered tokens, i.e., sentences or paragraphs. For the $n$-th
sample $D_{n}$, we write

$\displaystyle(\ell_{1}^{n},\dots,\ell^{n}_{\bar{T}_{\rm
p}}):=\left(\omega^{n,t},o_{1}^{n,t},g_{1}^{n,t},\dots,o_{H-1}^{n,t},g_{H-1}^{n,t},o_{H}^{n,t}\right)_{t\in[T_{\rm
p}]},$ (3.6)

with a length of $\bar{T}_{\rm p}=2HT_{\rm p}$, which contains $T_{\rm p}$
episodes with one task, $H$ observations and $H-1$ subgoals each. Following
this, LLM’s pretraining dataset is autoregressively constructed with the
expert guidance, denoted by
$\mathcal{D}_{\mathtt{LLM}}=\\{(\tilde{\ell}_{t}^{n},S_{t}^{n})\\}_{(n,t)\in[N_{\rm
p}]\times[\bar{T}_{\rm p}]}$, where $S_{t+1}^{n}=(S_{t}^{n},\ell^{n}_{t})$ and
let

$\left\\{\begin{aligned} &\tilde{\ell}_{t^{\prime}}^{n}=g_{h}^{n,t,*}\hskip
11.38092pt\text{if~{}}t^{\prime}=2H(t-1)+2h+1,\\\
&\tilde{\ell}_{t^{\prime}}^{n}=g_{h}^{n,t}\hskip
18.49411pt\text{otherwise}.\end{aligned}\right.$

In other words, when pretraining to predict the next subgoal, we replace the
one sampled from the behavior policy with the one from the optimal policy. In
practice, sentences with expert knowledge can be collected from online
knowledge platforms such as Wikipedia (Merity et al.,, 2016; Reid et al.,,
2022). Following the pretraining algorithm of BERT and GPT, the objective is
to minimize the cross-entropy loss, which can be summarized as
$\widehat{\theta}={\rm argmin}_{\theta\in\Theta}\
\mathcal{L}_{\mathrm{CE}}(\theta;\mathcal{D}_{\mathtt{LLM}})$ with

$\displaystyle\mathcal{L}_{\mathrm{CE}}(\theta;\mathcal{D}_{\mathtt{LLM}}):=\mathbb{\widehat{E}}_{\mathcal{D}_{\mathtt{LLM}}}\left[-\log\mathtt{LLM}_{\theta}(\ell\hskip
1.42262pt|\hskip 1.42262ptS)\right],$ (3.7)

and $\mathtt{LLM}_{\widehat{\theta}}$ is the pretrained LLM by algorithm in
(3.7). More details are deferred to §5.1.

#### Translator Pretraining.

To pretrain translators, we employ a self-supervised contrastive learning
approach, which aligns with celebrated vision-language models such as CLIP
(Radford et al.,, 2021) and ALIGN (Jia et al.,, 2021). Let
$\mathcal{D}_{\mathtt{Rep}}$ be the contrastive pretraining dataset for
translators, which is also constructed upon the dataset $\mathcal{D}$.
Following the framework adopted in Qiu et al., (2022); Zhang et al., (2022),
for each observation-state pair $(o,s)\in\mathcal{D}$, a positive or a
negative data point, labelled as $y=1$ and $y=0$, is generated with equal
probability, following that

  * -

Positive Data: Collect $(o,s)$ with label $y=1$.

  * -

Negative Data: Collect $(o,s^{-})$ with label $y=0$, where $s^{-}$ is sampled
from negative sampling distribution $\mathcal{P}^{-}\in\Delta(\mathcal{O})$
that has a full support over the domain of interest.

Denote $\mathbb{P}_{\mathcal{C}}$ as the joint distribution of data collected
by the process above. The learning algorithm follows that
$\widehat{\gamma}={\rm argmin}_{\gamma\in\Gamma}\
\mathcal{L}_{\mathrm{CT}}(\gamma;\mathcal{D}_{\mathtt{Rep}})$, where the
contrastive loss $\mathcal{L}_{\rm CT}(\gamma;\mathcal{D}_{\mathtt{Rep}})$ is
defined as

$\displaystyle\mathcal{L}_{\rm
CT}(\gamma;\mathcal{D}_{\mathtt{Rep}}):=\mathbb{\widehat{E}}_{\mathcal{D}_{\mathtt{Rep}}}[y\cdot\log\left(1+{f_{\gamma}(o,s)^{-1}}\right)+(1-y)\cdot\log\left({1+f_{\gamma}(o,s)}\right)].$
(3.8)

Consider function class $\mathcal{F}_{\gamma}$ with finite elements with
$\mathcal{F}_{\gamma}\subseteq(\mathcal{S}\times\mathcal{O}\mapsto\mathbb{R})$
serving as a set of candidate functions that approximates the ground-truth
likelihood ratio $f^{*}(\cdot,\cdot)=\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\cdot)/\mathcal{P}^{-}(\cdot)$ (see Lemma D.2 for justification).
Following this, the pretrained translator for the Reporter by the algorithm in
(3.8) is thus defined as $\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip
1.42262pt\cdot)=f_{\widehat{\gamma}}(\cdot,\cdot)\cdot\mathcal{P}^{-}(\cdot)$.
More details are deferred to §5.2.

######  Remark 3.1.

In (3.5), we assume that all pretraining data is generated from a joint
distribution $\mathbb{P}_{\mathcal{D}}$, and then split for pretraining of LLM
and Reporter. In practice, the pretraining dataset for the Reporter can
consist of paired observation-state data collected from any arbitrary
distribution, as long as (i) the LLM and Reporter “speak” the same language,
i.e., shared $\mathbb{O}$, and (ii) the coverage assumption can hold (see
Assumption 5.6).

######  Remark 3.2.

As an example, noise contrastive estimation (NCE, Gutmann and Hyvärinen,,
2010) is one of the most widely adopted objectives in contrastive
representation learning. From the theoretical lens, to estimate unnormalized
model $p_{d}$ with $x_{i}\overset{\rm iid}{\sim}p_{d}$, additional noise data
is sampled from a reference distribution $p_{n}$ and then estimate by
maximizing
$\widehat{\mathbb{E}}[y\cdot\log(h_{\gamma}(x))+(1-y)\cdot\log(1-h_{\gamma}(x))]$
with $y=\operatorname{\mathds{1}}(x\text{~{}is not noise})$ and
$h^{*}(x)=p_{d}(x)/(p_{d}(x)+p_{n}(x))$. With slight modifications, we use a
function class $\mathcal{F}$ to approximate the ratio $p_{d}/p_{n}$ rather
than the relative probability $h$ itself. In practice, the most commonly used
contrastive training objectives are variations of NCE and originated from the
NLP domain (Schiappa et al.,, 2023) by sharing the same idea of _minimizing
the distance between the positive pair and maximizing the distance between the
negative pairs_.

##  4 LLM Planning via Bayesian Aggregated Imitation Learning

In this section, we first demonstrate that LLMs can conduct high-level
planning through Bayesian aggregated imitation learning (BAIL) in §4.1,
leveraging the ICL ability of LLMs with the history-dependent prompts.
However, depending solely on LLM’s recommendations proves insufficient for
achieving sample efficiency under the worst case (see Proposition 4.3).
Following this, we propose a planning algorithm for Planner in §4.2,
leveraging LLMs for expert recommendations, in addition to an exploration
strategy.

###  4.1 Bayesian Aggregated Imitation Learning

In this subsection, we show that the LLM conducts high-level task planning via
BAIL, integrating both Bayesian model averaging (BMA, Hoeting et al.,, 1999)
during the online planning and imitation learning (IL, Ross and Bagnell,,
2010) during the offline pretraining. Intuitively, pretrained over
$\mathcal{D}_{\mathtt{LLM}}$, LLM approximates the conditional distribution
$\mathtt{LLM}(\ell=\cdot\hskip 1.42262pt|\hskip
1.42262ptS)=\mathbb{P}_{\mathcal{D}}(\ell=\cdot\hskip 1.42262pt|\hskip
1.42262ptS)$, where $\mathbb{P}_{\mathcal{D}}$ is the joint distribution in
(3.5) and the randomness introduced by the latent variable is aggregated,
i.e., $\mathbb{P}_{\mathcal{D}}(\ell=\cdot\hskip 1.42262pt|\hskip
1.42262ptS)=\mathbb{E}_{z\sim\mathbb{P}_{\mathcal{D}}(\cdot|S)}\left[\mathbb{P}_{\mathcal{D}}(\ell=\cdot\hskip
1.42262pt|\hskip 1.42262ptS,z)\right]$. Here,
$\mathbb{P}_{\mathcal{D}}(\ell=\cdot\hskip 1.42262pt|\hskip 1.42262ptS,z)$ can
be viewed as a generating distribution with a known $z$ and is then aggregated
over the posterior distribution $\mathbb{P}_{\mathcal{D}}(z=\cdot\hskip
1.42262pt|\hskip 1.42262ptS)$, aligning with the form of BMA (Zhang et al.,,
2023). We temporarily consider the perfect setting.

######  Definition 4.1 (Perfect Setting).

We say the PAR system is perfectly pretrained if (i)
$\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)=\mathbb{O}(\cdot\hskip 1.42262pt|\hskip 1.42262pts)$ for all
$s\in\mathcal{S}$, (ii) $\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip
1.42262pt|\hskip 1.42262ptS_{t})=\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262ptS_{t})$ for all $S_{t}=(\ell_{1},\dots,\ell_{t})\in\mathfrak{L}^{*}$
with length $t\leq\bar{T}_{\rm p}$.

The assumption states that the Reporter and LLMs can report and predict with
ground-truth distributions employed based on the joint distribution
$\mathbb{P}_{\mathcal{D}}$. During ICL, we invoke LLMs by history-dependent
$\mathtt{pt}_{h}^{t}=\mathcal{H}_{t}\cup\\{\omega^{t},\tau_{h}^{t}\\}\in\mathfrak{L}^{*}$
for all $(h,t)\in[H]\times[T]$. Conditioned on latent variable $z$ and
$\mathtt{pt}_{h}^{t}$, the generating distribution is the optimal policy such
that $\mathbb{P}_{\mathcal{D}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t},z)=\pi^{*}_{z,h}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})$, which is independent of historical
$\mathcal{H}_{t}$. In this sense, LLMs imitate expert policies during
pretraining. The proposition below shows that LLMs conduct task planning via
BAIL.

######  Proposition 4.2 (LLM Performs BAIL).

Assume that the pretraining data distribution is given by (3.5). Under the
perfect setting in Definition 4.1, for all $(h,t)\in[H]\times[T]$, the LLM
conducts task planning via BAIL, following that

$\displaystyle\pi_{h,\mathtt{LLM}}^{t}\left(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)=\sum_{z\in\mathcal{Z}}\pi^{*}_{z,h}\left(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right),$

where $\pi_{h,\mathtt{LLM}}^{t}$ denotes the LLM’s policy and prompt is
defined in (3.2).

###### Proof of Proposition 4.2..

Please refer to §C.1 for a detailed proof. ∎

Proposition 4.2 suggests that LLMs provide recommendations following a two-
fold procedure: Firstly, LLMs compute the posterior belief of each latent
variable $z\in\mathcal{Z}$ from $\mathtt{pt}_{h}^{t}$. Secondly, LLMs
aggregate the optimal policies over posterior probability and provide
recommendations.

###  4.2 LLM-Empowered Planning Algorithm

Algorithm 1 Planning with PAR System - Planner

1:Policy $\pi_{\mathtt{exp}}$ with $\eta\in(0,1)$, $c_{\mathcal{Z}}>0$, and
$|\mathcal{Z}|\in\mathbb{N}$.

2:$\mathcal{H}_{0}\leftarrow\\{\\}$, and
$\epsilon\leftarrow(H\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})/T\eta)^{1/2}$.

3:for episode $t$ from $1$ to $T$ do

4: Receive the high-level task $\omega^{t}$ from the human user.

5: Sample $\mathcal{I}_{t}\sim\text{Bernuolli}(\epsilon)$.

6: for step $h$ from $1$ to $H$ do

7: Collect the observation $o_{h}^{t}$ from the Reporter.

8: Set
$\mathtt{pt}_{h}^{t}\leftarrow\mathcal{H}_{t}\cup\\{\omega^{t},o_{1}^{t},\dots,o_{h}^{t}\\}$.

9: Sample $g_{h,\mathtt{LLM}}^{t}\sim\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})$ via prompting LLM.

10: If $\mathcal{I}_{t}=1$ then $g_{h}^{t}\leftarrow g_{h,\mathtt{LLM}}^{t}$,
else sample $g_{h}^{t}\sim\pi_{h,\mathtt{exp}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t})$.

11: Send the subgoal $g_{h}^{t}$ to the Actor.

12: end for

13: Update
$\mathcal{H}_{t+1}\leftarrow\mathcal{H}_{t}\cup\\{\omega^{t},\tau_{H}^{t}\\}$.

14:end for

Following the arguments above, we propose a planning algorithm for the Planner
within a perfect PAR system. From a high level, the process of task planning
is an implementation of policies from imitation learning (Ross and Bagnell,,
2010; Ross et al.,, 2011) with two key distinctions: (i) Planner collaborates
with LLM, a “nascent” expert that learns the hidden intricacies of the
external world from updating prompts; (ii) different from behavior cloning or
inverse RL, Planner does not aim to comprehend LLM’s behaviors. Instead, the
imitation is accomplished during the offline pretraining, and Planner shall
selectively adhere to LLM’s suggestions during online planning. Next, we show
that task planning solely guided by LLMs fails to achieve sample efficiency in
the worst case.

######  Proposition 4.3 (Hard-to-Distinguish Example).

Suppose that Definition 4.1 holds. Given any $T\in\mathbb{N}$, there exists an
HMDP and specific latent varibale $z\in\mathcal{Z}$ such that if Planner
strictly follows LLM’s recommended policies in Proposition 4.2, it holds that
${\rm Reg}_{z}(T)\geq 0.5T\cdot(1-1/|\mathcal{Z}|)^{T}$.

###### Proof of Proposition 4.3..

Please refer to §C.4 for a detailed proof. ∎

Proposition 4.3 indicates that relying solely on LLMs for task planning can
result in a suboptimal $\Omega(T)$ regret in the worst case when $|Z|=T$.
Thus, additional exploration is essential to discern the latent information
about the external world, a parallel to the practical implementations in
latent imitation learning (Edwards et al.,, 2019; Kidambi et al.,, 2021) and
LLM-based reasoning (Hao et al.,, 2023; Nottingham et al.,, 2023). In
practice, while the language model can guide achieving a goal, it’s important
to note that _this guidance is not grounded in real-world observations_. Thus,
as pointed out by Grigsby et al., (2023), the information provided in
narratives might be arbitrarily wrong, which highlights the need for
exploration to _navigate new environments effectively_. Similar to
$\epsilon$-greedy algorithms (Tokic and Palm,, 2011; Dann et al.,, 2022), we
provide a simple but efficient algorithm for LLM-empowered task planning.
Algorithm 1 gives the pseudocode. In each episode, the Planner performs two
main steps:

  * -

Policy Decision ($\mathtt{Line\ 5}$): Randomly decide whether to execute the
exploration policy $\pi_{\mathtt{exp}}$ or follow the LLM’s recommendations
within this episode with probability $\epsilon$.

  * -

Planning with LLMs ($\mathtt{Line\ 7-10}$): If Planner decides to follow the
LLM’s recommendations, the subgoal is obtained by prompting LLMs with
$\mathtt{pt}_{h}^{t}=\mathcal{H}_{t}\cup\\{\omega^{t},\tau_{h}^{t}\\}$,
equivalently sampling from $\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})$. Otherwise, the Planner takes sub-goal from
$\pi_{h,\mathtt{exp}}(\cdot\hskip 1.42262pt|\hskip 1.42262pt\tau_{h}^{t})$.

In conventional $\epsilon$-greedy algorithms, explorations are taken uniformly
over the action space $\mathcal{G}$, i.e., $\pi_{\mathtt{exp}}={\rm
Unif}_{\mathcal{G}}$. Recent work has extended it to a collection of
distributions (e.g., softmax, Gaussian noise) for function approximation (Dann
et al.,, 2022). Following this, we instead consider a broader class of
exploration strategies that satisfy the $\eta$-distinguishability property
below.

######  Definition 4.4 ($\eta$-distinguishability).

We say an exploration policy
$\pi_{\mathtt{exp}}=\\{\pi_{h,\mathtt{exp}}\\}_{h\in[H]}$ is
$\eta$-distinguishable if there exists an absolute constant $\eta>0$ such that
for all $z,z^{\prime}\in\mathcal{Z}$ with $z\neq z^{\prime}$, it holds that
$D_{\rm
H}^{2}\left(\mathbb{P}^{\pi_{\mathtt{exp}}}_{z}(\tau_{H}),\mathbb{P}^{\pi_{\mathtt{exp}}}_{z^{\prime}}\left(\tau_{H}\right)\right)\geq\eta$.

The $\eta$-distinguishability implies the existence of exploration policy
$\pi_{\mathtt{exp}}$ that could well-distinguish the models with an $\eta$-gap
in Hellinger distance concerning the distribution of whole trajectory, which
also impose condition over the model seperation. Next, we introduce the
assumption over priori.

######  Assumption 4.5 (Prior coverage).

There exists a constant $c_{\mathcal{Z}}>0$ such that
$\sup_{z,z^{\prime}}\frac{\mathcal{P}_{\mathcal{Z}}(z^{\prime})}{\mathcal{P}_{\mathcal{Z}}(z)}\leq
c_{\mathcal{Z}}$.

The assumption asserts a bounded ratio of priors, implying that each
$z\in\mathcal{Z}$ has a non-negligible prior probability. The assumption is
intuitive, as a negligible priori suggests such a scenario almost surely does
not occur, rendering the planning in such scenarios unnecessary. Now, we are
ready to present the main theorem of the Planner under perfect setting.

######  Theorem 4.6 (Regret under Perfect Setting).

Suppose that Definition 4.1 and Assumption 4.5 hold. Given an
$\eta$-distinguishable exploration policy $\pi_{\mathtt{exp}}$ and $T\leq
T_{\rm p}$, Algorithm 1 ensures

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle:=\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{J}_{z}(\pi_{z}^{*},\omega^{t})-\mathcal{J}_{z}(\pi^{t},\omega^{t})\right]\leq\tilde{\mathcal{O}}\left(H^{\frac{3}{2}}\sqrt{T/\eta\cdot\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})}\right),$

for any $z\in\mathcal{Z}$ and $\\{\omega^{t}\\}_{t\in[T]}$, if the Planner
explores with probability
$\epsilon=(H\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})/T\eta)^{1/2}$.

###### Proof of Theorem 4.6..

Please refer to §C.2 for a detailed proof. ∎

Theorem 4.6 states that the Planner’s algorithm can attain a
$\tilde{\mathcal{O}}(\sqrt{T})$ regret for planning facilitated by LLMs. The
multiplicative factor of the regret depends on the horizon of the interactive
process $H$, the reciprocal of coverage rate $\eta$ in Definition 4.4, and the
logarithmic term $\log\left(c_{\mathcal{Z}}|\mathcal{Z}|\right)$ including
both the cardinality of candidate models and the prior coverage in Assumption
4.5, which jointly characterizes the complexity of the physical world.

######  Remark 4.7.

Lee et al., (2023) has demonstrated that a perfect decision-pretrained
transformer, similar to the role of LLM in ours, can attain a
$\tilde{\mathcal{O}}(H^{\frac{3}{2}}\sqrt{T})$ Bayesian regret, i.e.,
$\mathbb{E}_{z\sim\mathcal{P}_{\mathcal{Z}}}[{\rm Reg}(T)]$, via ICL. In
comparison, we focus on a more challenging setting that aims to control the
frequentist regret, which is closer to applications, and attain a comparable
result with additional exploration.

##  5 Performance under Practical Setting

###  5.1 Pretraining Large Language Model

In this subsection, we elaborate on the pretraining of LLMs using transformer
architecture. We employ a supervised learning algorithm minimizing the cross-
entropy loss, i.e., $\widehat{\theta}={\rm argmin}_{\theta\in\Theta}\
\mathcal{L}_{\mathrm{CE}}(\theta;\mathcal{D}_{\mathtt{LLM}})$, as detailed in
(3.8). Following this, the population risk follows that

$\displaystyle\mathcal{R}_{\mathrm{CE}}(\theta;\mathcal{D}_{\mathtt{LLM}})=\mathbb{E}_{t}[\mathbb{E}_{S_{t}}[D_{\rm
KL}(\mathtt{LLM}(\cdot|S_{t})\hskip 1.42262pt\|\hskip
1.42262pt\mathtt{LLM}_{\theta}(\cdot|S_{t}))+{\rm
Ent}(\mathtt{LLM}(\cdot|S_{t}))]],$

where $t\sim{\rm Unif}({[\bar{T}_{\rm p}]})$, $S_{t}$ is distributed as the
pretraining distribution, and ${\rm
Ent}(\mathbb{P})=\mathbb{E}_{x\sim\mathbb{P}}[\log\mathbb{P}(x)]$ is the
Shannon entropy. As the minimum is achieved at
$\mathtt{LLM}_{\theta}(\cdot|S)=\mathtt{LLM}(\cdot|S)$, estimated
$\mathtt{LLM}_{\widehat{\theta}}$ and $\mathtt{LLM}$ are expected to converge
under the algorithm with a sufficiently large dataset. Specifically, our
design adopts a transformer function class to stay consistent with the
architectural choices of language models like BERT and GPT. Specifically, a
transformer model comprises $D$ sub-modules, with each sub-module
incorporating a Multi-Head Attention (MHA) mechanism and a fully connected
Feed-Forward (FF) layer. See §A.2 for further details, and we specify two
widely adopted assumptions in the theoretical analysis of LLM pretraining
(Wies et al.,, 2023; Zhang et al.,, 2023).

######  Assumption 5.1 (Boundedness).

For all $z\in\mathcal{Z}$ and $t\leq\bar{T}_{\rm p}$, there exists a constant
$R>0$ such that all
$S_{t}=(\ell_{1},\dots,\ell_{t})\sim\mathbb{P}_{\mathcal{D}}(\cdot\hskip
1.42262pt|\hskip 1.42262ptz)$ with $S_{t}\in\mathfrak{L}^{*}$ satisfies that
$\|S_{t}\|_{2,\infty}\leq R$ almost surely.

The boundedness assumption requires that the $\ell_{2}$-norm of the magnitude
of each token is upper bounded by $R>0$, and such an assumption holds in most
settings.

######  Assumption 5.2 (Ambiguity).

For all latent variable $z\in\mathcal{Z}$, there exists a constant $c_{0}>0$
such that for all $\ell_{t+1}\in\mathfrak{L}$ and
$S_{t}=(\ell_{1},\dots,\ell_{t})\in\mathfrak{L}^{*}$ with length
$t<\bar{T}_{\rm p}$, it holds $\mathbb{P}_{\mathcal{D}}(\ell_{t+1}\hskip
1.42262pt|\hskip 1.42262ptS_{t},z)\geq c_{0}$.

The ambiguity assumption states that the generating distribution is lower
bounded, and the assumption is grounded in reasoning as there may be multiple
plausible choices for the subsequent words to convey the same meaning. Next,
we present the performance of the pretrained LLMs.

######  Theorem 5.3 (Zhang et al., (2023)).

Suppose that Assumptions 5.1 and 5.2 hold. With probability at least
$1-\delta$, the pretrained model $\mathtt{LLM}_{\widehat{\theta}}$ by the
algorithm in (3.7) satisfies that

$\displaystyle\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{LLM}}}\left[D_{\rm
TV}\left(\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262ptS),\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip 1.42262pt|\hskip
1.42262ptS)\right)\right]$
$\displaystyle\quad{\leq\mathcal{O}\biggl{(}\inf_{\theta^{*}\in\Theta}\sqrt{\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{LLM}}}\left[D_{\mathrm{KL}}\left(\mathtt{LLM}(\cdot\hskip
1.42262pt|\hskip 1.42262ptS),\mathtt{LLM}_{\theta^{*}}(\cdot\hskip
1.42262pt|\hskip 1.42262ptS)\right)\right]}}$
$\displaystyle\qquad+\frac{t_{\rm
mix}^{1/4}\log\frac{1}{\delta}}{(N_{\mathrm{p}}\bar{T}_{\mathrm{p}})^{1/4}}+\sqrt{\frac{t_{\rm
mix}}{N_{\mathrm{p}}\bar{T}_{\mathrm{p}}}}\biggl{(}\bar{D}\log\bigl{(}1+\bar{B}N_{\mathrm{p}}\bar{T}_{\mathrm{p}}\bigr{)}+\log\frac{1}{\delta}\biggl{)}\biggl{)},$

where $\bar{B}$ and $\bar{D}$ features the tranformer’s architecture, $t_{\rm
mix}$ denotes the mixing time of Markov chain $\\{S_{t}\\}_{t\in[T]}$222Note
that $\\{S^{n}_{t}\\}_{t\in[T]}$ directly satisfies Markov property since
$S_{t}^{n}=(\ell_{1}^{n},\dots,\ell_{t}^{n})$ and thus $S^{n}_{i}\subseteq
S^{n}_{t}$ for all $i\leq t$., and $N_{\mathrm{p}}\bar{T}_{\mathrm{p}}$ is the
size of dataset $\mathcal{D}_{\mathtt{LLM}}$. See §A.2 for detailed structure
and definitions.

###### Proof of Theorem 2..

Please refer to Theorem 5.3 in Zhang et al., (2023) for a detailed proof. ∎

Theorem 2 states that the total variation of the conditional distribution,
with expectation taken over the average distribution of context $S$ in
$\mathcal{D}_{\mathtt{LLM}}$ (see Table 1 for definition), converges at
$\mathcal{O}\left((N_{\mathrm{p}}\bar{T}_{\mathrm{p}})^{-1/2}\right)$. Note
that the first two terms represent the approximation error and deep neural
networks act as a universal approximator (Yarotsky,, 2017) such that the error
would vanish with increasing volume of network (Proposition C.4, Zhang et
al.,, 2023). For notational simplicity, we denote the right-hand side of
theorem as $\Delta_{\mathtt{LLM}}(N_{\rm p},T_{\rm p},H,\delta)$.

###  5.2 Pretraining Observation-to-Language Translator

In this subsection, we focus on the pretraining of observation-to-language
translators under a self-supervised learning architecture using the
contrastive loss. Consider the function class

$\mathcal{F}_{\gamma}=\\{f_{\gamma}(\cdot,\cdot):\gamma\in\Gamma,\|f_{\gamma}\|_{\infty}\leq
B_{\mathcal{F}},\|1/f_{\gamma}\|_{\infty}\leq B^{-}_{\mathcal{F}}\\},$

with finite elements, and the contrastive loss $\mathcal{L}_{\rm
CT}(\gamma;\mathcal{D}_{\mathtt{Rep}})$ in (3.8) is then defined over
$\mathcal{F}_{\gamma}$. Note that the contrastive loss can be equivalently
written as the negative log-likelihood loss of a binary discriminator,
following that $\mathcal{L}_{\rm
CT}(\gamma;\mathcal{D}_{\mathtt{Rep}})=\mathbb{\widehat{E}}_{\mathcal{D}_{\mathtt{Rep}}}\left[-\mathbb{D}_{\gamma}(y\hskip
1.42262pt|\hskip 1.42262pto,s)\right]$, where we define

$\displaystyle\mathbb{D}_{\gamma}(y\hskip 1.42262pt|\hskip
1.42262pto,s):=\left(\frac{f_{\gamma}(o,s)}{1+f_{\gamma}(o,s)}\right)^{y}\left(\frac{1}{1+f_{\gamma}(o,s)}\right)^{1-y}.$
(5.1)

Based on (5.1) and the algorithm $\widehat{\gamma}={\rm
argmin}_{\gamma\in\Gamma}\
\mathcal{L}_{\mathrm{CT}}(\gamma;\mathcal{D}_{\mathtt{Rep}})$, the population
risk follows that

$\displaystyle\mathcal{R}_{\rm
CT}(\gamma;\mathcal{D}_{\mathtt{Rep}})=\mathbb{E}\left[D_{\rm
KL}\left(\mathbb{D}_{\gamma}(\cdot|o,s)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{D}(\cdot|o,s)\right)+{\rm
Ent}(\mathbb{D}(\cdot|o,s))\right].$ (5.2)

As the minimum is attained at $\mathbb{D}_{\gamma}(\cdot\hskip
1.42262pt|\hskip 1.42262pto,s)=\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)$, where $\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s):=\mathbb{P}_{\mathcal{C}}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)$ is the distribution of the label conditioned on the $(o,s)$
pair in contrastive data collection, estimated
$\mathbb{D}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip 1.42262pto,s)$ and
$\mathbb{D}(\cdot\hskip 1.42262pt|\hskip 1.42262pto,s)$ are expected to
converge, and thus the learning target is the ground-truth likelihood ratio
$f^{*}(o,s)=\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)/\mathcal{P}^{-}(o)$ (see Lemma D.2). Below, we assume the learning
target $f^{*}(o,s)$ is realizable in $\mathcal{F}_{\gamma}$, which is standard
in literature (Qiu et al.,, 2022).

######  Assumption 5.4 (Realizability).

Given a designated negative sampling distribution
$\mathcal{P}^{-}\in\Delta(\mathcal{O})$, there exists $\gamma^{*}\in\Gamma$
such that $f_{\gamma^{*}}(o,s)=\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)/\mathcal{P}^{-}(o)$ for all
$(o,s)\in\mathcal{O}\times\mathcal{S}$.

Next we present the performance of the pretrained translator.

######  Theorem 5.5 (Pretrained Translator).

Suppose that Assumption 5.4 holds. With probability at least $1-\delta$, the
pretrained model $\mathbb{O}_{\widehat{\gamma}}$ by the algorithm in (5.1)
satisfies that

$\displaystyle\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{Rep}}}\left[D_{\rm
TV}\left(\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts),\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\right)\right]\leq\mathcal{O}\left(\frac{B_{\mathcal{F}}(B^{-}_{\mathcal{F}})^{1/2}}{(N_{\rm
p}T_{\rm p}H)^{1/2}}\sqrt{\log(N_{\rm p}T_{\rm
p}H|\mathcal{F}_{\gamma}|/\delta)}\right),$

where let $\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)=f_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\cdot\mathcal{P}^{-}(\cdot)$ and $|\mathcal{F}_{\gamma}|$ denotes
the cardinality of the function class $\mathcal{F}_{\gamma}$.

###### Proof of Theorem 5.5..

Please refer to §D.1 for a detailed proof. ∎

Theorem 5.5 posits that the average expectation of the total variation of the
translation distribution regarding $\mathcal{D}_{\mathtt{Rep}}$ converges at
$\mathcal{O}\left((N_{\mathrm{p}}{T}_{\mathrm{p}})^{-1/2}\right)$. For
notational simplicity, write the right-hand side of the theorem as
$\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm p},H,\delta)$. Furthermore, the
algorithm also ensures a more stringent convergence guarantee concerning
$\chi^{2}$-divergence:
$\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{Rep}}}[\chi^{2}(\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts))]\leq\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm p},H,\delta)^{2}$.

###  5.3 Performance with Pretrained PAR System

In this subsection, we delve into the performance of task planning with
pretrained PAR system. We first introduce the online coverage assumption,
which pertains to the distribution of online planning trajectories under
practical scenarios and trajectories in pretraining datasets.

######  Assumption 5.6 (Coverage).

There exists absolute constants $\lambda_{S}>0$ and $\lambda_{R}>0$ such that
for all latent variable $z\in\mathcal{Z}$, $t<\bar{T}_{\rm p}$ and policy
sequence $\\{\pi^{i}\\}_{i\leq\lceil t/2H\rceil}$ from the Planner, it holds
that (i) $\prod_{i=1}^{\lceil
t/2H\rceil}\mathbb{\widehat{P}}_{z}^{\pi_{i}}(\tilde{S_{i}})\leq\lambda_{S}\cdot\bar{\mathbb{P}}_{\mathcal{D}_{\mathtt{LLM}}}(S_{t})$
for all ordered sequence $S_{t}=(\tilde{S}_{i})_{i\leq\lceil
t/2H\rceil}\in\mathfrak{L}^{*}$, where $|\tilde{S}_{i}|=2H$ for all $k<\lceil
t/2H\rceil$, and (ii)
$\bar{\mathbb{P}}_{\mathcal{D}_{\mathtt{Rep}}}(s)\geq\lambda_{R}$ for all
state $s\in\mathcal{S}$.

Here, $\mathbb{\widehat{P}}_{z}$ denotes the distribution of the dynamic
system with the pretrained translator. The assumption asserts that (i)
distribution of the ICL prompts induced by policy sequences
$\\{\pi^{i}\\}_{i\leq\lceil t/2H\rceil}$ from the Planner under practical
scenarios is covered by the pretraining data, where $\lceil t/2H\rceil$
denotes the number of episodes described in $S_{t}$. (ii) all states
$s\in\mathcal{S}$ are covered by the average distribution of the Reporter’s
pretraining dataset. Similar conditions are adopted in ICL analysis (Zhang et
al.,, 2023), decision pretrained transformer (Lee et al.,, 2023; Lin et al.,
2023b, ) and offline RL (Munos,, 2005; Duan et al.,, 2020). Intuitively, LLM
and reporter cannot precisely plan or translate beyond the support of the
pretraining dataset. These conditions are achievable if an explorative
behavior strategy $\pi^{b}$ is deployed with a sufficiently large $N_{\rm p}$
when collecting data. We then present the main theorem regarding the practical
performance.

######  Theorem 5.7 (Regret under Practical Setting).

Suppose that Assumptions 4.5, 5.1, 5.2, 5.4 and 5.6. Given an
$\eta$-distinguishable exploration policy $\pi_{\mathtt{exp}}$ and $T\leq
T_{\rm p}$, under the practical setting, the Planner’s algorithm in Algorithm
1 ensures that

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\tilde{\mathcal{O}}\Big{(}H^{\frac{3}{2}}\sqrt{T/\eta\cdot\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})}+H^{2}T\cdot\Delta_{\rm
p}(N_{\rm p},T_{\rm p},H,1\sqrt{T},\xi)\Big{)},$

for any $z\in\mathcal{Z}$ and $\\{\omega_{t}\\}_{t\in[T]}$. The cumulative
pretraining error of PAR system follows that

$\displaystyle\Delta_{\rm p}$ $\displaystyle(N_{\rm p},T_{\rm
p},H,\delta,\xi)=(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}$
$\displaystyle+2\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)+\lambda_{S}\cdot\Delta_{\mathtt{LLM}}(N_{\rm p},T_{\rm
p},H,\delta).$

where $\xi=(\eta,\lambda_{S},\lambda_{R})$ are defined in Definition 4.4 and
Assumption 5.6, and pretraining errors $\Delta_{\mathtt{LLM}}$ and
$\Delta_{\mathtt{Rep}}$ are defined in Theorem 2 and Theorem 5.5. Under the
practical setting, Planner should explore with probability
$\epsilon=\big{(}H\log\big{(}c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T}\big{)}/T\eta\big{)}^{1/2}+H(\eta\lambda_{\min})^{-1}\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,1/\sqrt{T})^{2}$.

###### Proof of Theorem 5.7..

Please refer to §D.2 for a detailed proof. ∎

Theorem 5.7 reveals that, in comparison to perfect scenario, the Planner can
achieve an approximate $\tilde{\mathcal{O}}(\sqrt{T})$ regret, but
incorporating an additional pretraining error term that could diminishe with
an increase in the volume of pretraining data. Besides, it further underscores
the necessity of exploration, where the Planner should explore with an
additional $H(\eta\lambda_{\min})^{-1}\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}$ to handle the mismatch between the ground-truth and the
pretrained environment.

######  Remark 5.8.

The challenge of establishing a performance guarantee in a practical setting
arises from the mismatch between the ground-truth environment and the
pretrained one, leading to a distributional shift in posterior probability.
Besides, BAIL is realized through a pretrained LLM, which introduces its
pretraining error inaddition. In response, we propose a novel regret
decomposition and provide the convergence rate of posterior probability with
bounded pretraining errors, distinguishing ours from the previous results in
Lee et al., (2023); Liu et al., (2023).

#### Extentions.

We also present two extensions. In §B.1, we discuss the design of Planner by
taking LLMs as World Model (WM). Here, the Planner prompts the LLM to predict
the next observation rather than subgoals, alleviating the reliance on expert
knowledge. By leveraging model-based RL methods like Monte Carlo Tree Search
(MCTS) and Real-Time Dynamic Programming (RTDP), the Planner utilizes the LLM-
simulated environment to optimize its strategies based on the contextual
information. As shown in Proposition B.1, the simulated world model via ICL
conforms to Bayesian Aggregated World Model (BAWM). Hence, the LLM Planner
achieves a regret at rate of ${\rm
Reg}_{z}(T)\leq\tilde{\mathcal{O}}(H\sqrt{T/\eta})+H^{2}T\cdot\Delta_{\rm
p,wm}$ under practical setting with regularity conditions (see Corollary B.3).
Besides, we extend the results in §4 to accommodate the scenario of multi-
agent collaboration, i.e., $K$ Actors. In §B.2, we formulate the probelm as a
cooperative hierarchical Markov Game (HMG) and establish a theoretical
guarantee of ${\rm Reg}_{z}(T)\leq\tilde{\mathcal{O}}(\sqrt{H^{3}TK/\eta})$
under the perfect setting (see Corollary B.4). These two extention correponds
to recent works on LLM planning as world model (e.g., Hu and Shu,, 2023) and
muti-agent collaboration of LLM Agents (e.g., Mandi et al.,, 2023).

##  6 Conclusion

In this work, we embedded the LLM-empowered decision-making problem into a
hierarchical RL framework named PAR system where at the high level, the LLM
Planner decomposes the user-specified task into subgoals, and at the low
level, the Actor(s) translate the linguistic subgoals into physical
realizations while also providing feedbacks for augmenting the planning
process through a trained reporter. Under the perfect setting, we characterize
the BAIL nature of the LLM-aided planning pipeline and the nessecity of
exploration even under expert guidance. We also shed light on how the training
errors of both LLM and reporter enter the ICL error under practical scenarios.

## References

  * Agarwal et al., (2020) Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020).  Flambe: Structural complexity and representation learning of low rank mdps.  Advances in neural information processing systems, 33:20095–20107.
  * Ahuja et al., (2023) Ahuja, K., Panwar, M., and Goyal, N. (2023).  In-context learning through the bayesian prism.  arXiv preprint arXiv:2306.04891.
  * Barto et al., (1995) Barto, A. G., Bradtke, S. J., and Singh, S. P. (1995).  Learning to act using real-time dynamic programming.  Artificial intelligence, 72(1-2):81–138.
  * Barto and Mahadevan, (2003) Barto, A. G. and Mahadevan, S. (2003).  Recent advances in hierarchical reinforcement learning.  Discrete event dynamic systems, 13(1-2):41–77.
  * Başar and Olsder, (1998) Başar, T. and Olsder, G. J. (1998).  Dynamic noncooperative game theory.  SIAM.
  * Blei et al., (2003) Blei, D. M., Ng, A. Y., and Jordan, M. I. (2003).  Latent dirichlet allocation.  Journal of machine Learning research, 3(Jan):993–1022.
  * Bonet and Geffner, (2001) Bonet, B. and Geffner, H. (2001).  Planning as heuristic search.  Artificial Intelligence, 129(1-2):5–33.
  * Brohan et al., (2023) Brohan, A., Chebotar, Y., Finn, C., Hausman, K., Herzog, A., Ho, D., Ibarz, J., Irpan, A., Jang, E., Julian, R., et al. (2023).  Do as i can, not as i say: Grounding language in robotic affordances.  In Conference on Robot Learning, pages 287–318. PMLR.
  * Brown et al., (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020).  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901.
  * Browne et al., (2012) Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. (2012).  A survey of monte carlo tree search methods.  IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43.
  * Chan et al., (2022) Chan, S. C., Santoro, A., Lampinen, A. K., Wang, J. X., Singh, A., Richemond, P. H., McClelland, J., and Hill, F. (2022).  Data distributional properties drive emergent few-shot learning in transformers.  arXiv preprint arXiv:2205.05055.
  * Chane-Sane et al., (2021) Chane-Sane, E., Schmid, C., and Laptev, I. (2021).  Goal-conditioned reinforcement learning with imagined subgoals.  In International Conference on Machine Learning, pages 1430–1440. PMLR.
  * Dann et al., (2022) Dann, C., Mansour, Y., Mohri, M., Sekhari, A., and Sridharan, K. (2022).  Guarantees for epsilon-greedy reinforcement learning with function approximation.  In International conference on machine learning, pages 4666–4689. PMLR.
  * Devlin et al., (2018) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2018).  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805.
  * Donsker and Varadhan, (1976) Donsker, M. D. and Varadhan, S. S. (1976).  Asymptotic evaluation of certain markov process expectations for large time—iii.  Communications on pure and applied Mathematics, 29(4):389–461.
  * Du et al., (2023) Du, Y., Yang, M., Florence, P., Xia, F., Wahid, A., Ichter, B., Sermanet, P., Yu, T., Abbeel, P., Tenenbaum, J. B., et al. (2023).  Video language planning.  arXiv preprint arXiv:2310.10625.
  * Duan et al., (2020) Duan, Y., Jia, Z., and Wang, M. (2020).  Minimax-optimal off-policy evaluation with linear function approximation.  In International Conference on Machine Learning, pages 2701–2709. PMLR.
  * Edwards et al., (2019) Edwards, A., Sahni, H., Schroecker, Y., and Isbell, C. (2019).  Imitating latent policies from observation.  In International conference on machine learning, pages 1755–1763. PMLR.
  * Foster et al., (2021) Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021).  The statistical complexity of interactive decision making.  arXiv preprint arXiv:2112.13487.
  * Fu et al., (2024) Fu, D., Li, X., Wen, L., Dou, M., Cai, P., Shi, B., and Qiao, Y. (2024).  Drive like a human: Rethinking autonomous driving with large language models.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 910–919.
  * Garg et al., (2022) Garg, S., Tsipras, D., Liang, P. S., and Valiant, G. (2022).  What can transformers learn in-context? a case study of simple function classes.  Advances in Neural Information Processing Systems, 35:30583–30598.
  * Geer, (2000) Geer, S. A. (2000).  Empirical Processes in M-estimation, volume 6.  Cambridge university press.
  * Ghallab et al., (2004) Ghallab, M., Nau, D., and Traverso, P. (2004).  Automated Planning: theory and practice.  Elsevier.
  * Grigsby et al., (2023) Grigsby, J., Fan, L., and Zhu, Y. (2023).  Amago: Scalable in-context reinforcement learning for adaptive agents.  arXiv preprint arXiv:2310.09971.
  * Gutmann and Hyvärinen, (2010) Gutmann, M. and Hyvärinen, A. (2010).  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 297–304. JMLR Workshop and Conference Proceedings.
  * Hahn and Goyal, (2023) Hahn, M. and Goyal, N. (2023).  A theory of emergent in-context learning as implicit structure induction.  arXiv preprint arXiv:2303.07971.
  * Hao et al., (2023) Hao, S., Gu, Y., Ma, H., Hong, J. J., Wang, Z., Wang, D. Z., and Hu, Z. (2023).  Reasoning with language model is planning with world model.  arXiv preprint arXiv:2305.14992.
  * Hoeting et al., (1999) Hoeting, J. A., Madigan, D., Raftery, A. E., and Volinsky, C. T. (1999).  Bayesian model averaging: a tutorial.  Statistical science, 14(4):382–417.
  * Honovich et al., (2022) Honovich, O., Shaham, U., Bowman, S. R., and Levy, O. (2022).  Instruction induction: From few examples to natural language task descriptions.  arXiv preprint arXiv:2205.10782.
  * Hu et al., (2023) Hu, M., Mu, Y., Yu, X., Ding, M., Wu, S., Shao, W., Chen, Q., Wang, B., Qiao, Y., and Luo, P. (2023).  Tree-planner: Efficient close-loop task planning with large language models.  arXiv preprint arXiv:2310.08582.
  * Hu and Shu, (2023) Hu, Z. and Shu, T. (2023).  Language models, agent models, and world models: The law for machine reasoning and planning.  arXiv preprint arXiv:2312.05230.
  * Huang et al., (2022) Huang, W., Abbeel, P., Pathak, D., and Mordatch, I. (2022).  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In International Conference on Machine Learning, pages 9118–9147. PMLR.
  * Iyer et al., (2022) Iyer, S., Lin, X. V., Pasunuru, R., Mihaylov, T., Simig, D., Yu, P., Shuster, K., Wang, T., Liu, Q., Koura, P. S., et al. (2022).  Opt-iml: Scaling language model instruction meta learning through the lens of generalization.  arXiv preprint arXiv:2212.12017.
  * Jia et al., (2021) Jia, C., Yang, Y., Xia, Y., Chen, Y.-T., Parekh, Z., Pham, H., Le, Q., Sung, Y.-H., Li, Z., and Duerig, T. (2021).  Scaling up visual and vision-language representation learning with noisy text supervision.  In International conference on machine learning, pages 4904–4916. PMLR.
  * Jiang, (2023) Jiang, H. (2023).  A latent space theory for emergent abilities in large language models.  arXiv preprint arXiv:2304.09960.
  * Kidambi et al., (2021) Kidambi, R., Chang, J., and Sun, W. (2021).  Mobile: Model-based imitation learning from observation alone.  Advances in Neural Information Processing Systems, 34:28598–28611.
  * Kim et al., (2022) Kim, H. J., Cho, H., Kim, J., Kim, T., Yoo, K. M., and Lee, S.-g. (2022).  Self-generated in-context learning: Leveraging auto-regressive language models as a demonstration generator.  arXiv preprint arXiv:2206.08082.
  * Kusner et al., (2017) Kusner, M. J., Paige, B., and Hernández-Lobato, J. M. (2017).  Grammar variational autoencoder.  In International conference on machine learning, pages 1945–1954. PMLR.
  * Lee et al., (2023) Lee, J. N., Xie, A., Pacchiano, A., Chandak, Y., Finn, C., Nachum, O., and Brunskill, E. (2023).  Supervised pretraining can learn in-context reinforcement learning.  arXiv preprint arXiv:2306.14892.
  * (40) Li, B., Wu, P., Abbeel, P., and Malik, J. (2023a).  Interactive task planning with language models.  arXiv preprint arXiv:2310.10645.
  * (41) Li, C., Gan, Z., Yang, Z., Yang, J., Li, L., Wang, L., and Gao, J. (2023b).  Multimodal foundation models: From specialists to general-purpose assistants.  arXiv preprint arXiv:2309.10020, 1(2):2.
  * Li et al., (2022) Li, S., Puig, X., Paxton, C., Du, Y., Wang, C., Fan, L., Chen, T., Huang, D.-A., Akyürek, E., Anandkumar, A., et al. (2022).  Pre-trained language models for interactive decision-making.  Advances in Neural Information Processing Systems, 35:31199–31212.
  * (43) Lin, B. Y., Huang, C., Liu, Q., Gu, W., Sommerer, S., and Ren, X. (2023a).  On grounded planning for embodied tasks with language models.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 13192–13200.
  * (44) Lin, L., Bai, Y., and Mei, S. (2023b).  Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining.  arXiv preprint arXiv:2310.08566.
  * Liu et al., (2021) Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W. (2021).  What makes good in-context examples for gpt-$3$?  arXiv preprint arXiv:2101.06804.
  * (46) Liu, M., Zhu, M., and Zhang, W. (2022a).  Goal-conditioned reinforcement learning: Problems and solutions.  arXiv preprint arXiv:2201.08299.
  * (47) Liu, X., Ji, K., Fu, Y., Tam, W., Du, Z., Yang, Z., and Tang, J. (2022b).  P-tuning: Prompt tuning can be comparable to fine-tuning across scales and tasks.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 61–68.
  * Liu et al., (2023) Liu, Z., Hu, H., Zhang, S., Guo, H., Ke, S., Liu, B., and Wang, Z. (2023).  Reason for future, act for now: A principled framework for autonomous llm agents with provable sample efficiency.  arXiv preprint arXiv:2309.17382.
  * Mandi et al., (2023) Mandi, Z., Jain, S., and Song, S. (2023).  Roco: Dialectic multi-robot collaboration with large language models.  arXiv preprint arXiv:2307.04738.
  * Merity et al., (2016) Merity, S., Xiong, C., Bradbury, J., and Socher, R. (2016).  Pointer sentinel mixture models.  arXiv preprint arXiv:1609.07843.
  * Michel et al., (2019) Michel, P., Levy, O., and Neubig, G. (2019).  Are sixteen heads really better than one?  Advances in neural information processing systems, 32.
  * Munos, (2005) Munos, R. (2005).  Error bounds for approximate value iteration.  In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999.
  * Nottingham et al., (2023) Nottingham, K., Ammanabrolu, P., Suhr, A., Choi, Y., Hajishirzi, H., Singh, S., and Fox, R. (2023).  Do embodied agents dream of pixelated sheep?: Embodied decision making using language guided world modelling.  arXiv preprint arXiv:2301.12050.
  * OpenAI, (2023) OpenAI, R. (2023).  Gpt-4 technical report.  arXiv, pages 2303–08774.
  * Pateria et al., (2021) Pateria, S., Subagdja, B., Tan, A.-h., and Quek, C. (2021).  Hierarchical reinforcement learning: A comprehensive survey.  ACM Computing Surveys (CSUR), 54(5):1–35.
  * Paulin, (2015) Paulin, D. (2015).  Concentration inequalities for markov chains by marton couplings and spectral methods.
  * Polyanskiy and Wu, (2022) Polyanskiy, Y. and Wu, Y. (2022).  Information theory: From coding to learning.  Book draft.
  * Qiu et al., (2022) Qiu, S., Wang, L., Bai, C., Yang, Z., and Wang, Z. (2022).  Contrastive ucb: Provably efficient contrastive self-supervised learning in online reinforcement learning.  In International Conference on Machine Learning, pages 18168–18210. PMLR.
  * Radford et al., (2021) Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. (2021).  Learning transferable visual models from natural language supervision.  In International conference on machine learning, pages 8748–8763. PMLR.
  * Raffel et al., (2020) Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. (2020).  Exploring the limits of transfer learning with a unified text-to-text transformer.  The Journal of Machine Learning Research, 21(1):5485–5551.
  * Reid et al., (2022) Reid, M., Yamada, Y., and Gu, S. S. (2022).  Can wikipedia help offline reinforcement learning?  arXiv preprint arXiv:2201.12122.
  * Ross and Bagnell, (2010) Ross, S. and Bagnell, D. (2010).  Efficient reductions for imitation learning.  In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661–668. JMLR Workshop and Conference Proceedings.
  * Ross et al., (2011) Ross, S., Gordon, G., and Bagnell, D. (2011).  A reduction of imitation learning and structured prediction to no-regret online learning.  In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627–635. JMLR Workshop and Conference Proceedings.
  * Schiappa et al., (2023) Schiappa, M. C., Rawat, Y. S., and Shah, M. (2023).  Self-supervised learning for videos: A survey.  ACM Computing Surveys, 55(13s):1–37.
  * Singh et al., (2023) Singh, I., Blukis, V., Mousavian, A., Goyal, A., Xu, D., Tremblay, J., Fox, D., Thomason, J., and Garg, A. (2023).  Progprompt: Generating situated robot task plans using large language models.  In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 11523–11530. IEEE.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Team et al., (2023) Team, G., Anil, R., Borgeaud, S., Wu, Y., Alayrac, J.-B., Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M., Hauth, A., et al. (2023).  Gemini: a family of highly capable multimodal models.  arXiv preprint arXiv:2312.11805.
  * Tokic and Palm, (2011) Tokic, M. and Palm, G. (2011).  Value-difference based exploration: adaptive control between epsilon-greedy and softmax.  In Annual conference on artificial intelligence, pages 335–346. Springer.
  * Touvron et al., (2023) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. (2023).  Llama 2: Open foundation and fine-tuned chat models.  arXiv preprint arXiv:2307.09288.
  * Van Handel, (2014) Van Handel, R. (2014).  Probability in high dimension.  Lecture Notes (Princeton University).
  * (71) Wang, X., Zhu, W., Saxon, M., Steyvers, M., and Wang, W. Y. (2023a).  Large language models are latent variable models: Explaining and finding good demonstrations for in-context learning.  In Thirty-seventh Conference on Neural Information Processing Systems.
  * (72) Wang, Y., Jiao, R., Lang, C., Zhan, S. S., Huang, C., Wang, Z., Yang, Z., and Zhu, Q. (2023b).  Empowering autonomous driving with large language models: A safety perspective.  arXiv preprint arXiv:2312.00812.
  * (73) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al. (2022a).  Emergent abilities of large language models.  arXiv preprint arXiv:2206.07682.
  * (74) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. (2022b).  Chain-of-thought prompting elicits reasoning in large language models.  Advances in Neural Information Processing Systems, 35:24824–24837.
  * Wies et al., (2023) Wies, N., Levine, Y., and Shashua, A. (2023).  The learnability of in-context learning.  arXiv preprint arXiv:2303.07895.
  * Xie et al., (2021) Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. (2021).  An explanation of in-context learning as implicit bayesian inference.  arXiv preprint arXiv:2111.02080.
  * Xu et al., (2023) Xu, P., Zhu, X., and Clifton, D. A. (2023).  Multimodal learning with transformers: A survey.  IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * (78) Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., and Narasimhan, K. (2023a).  Tree of thoughts: Deliberate problem solving with large language models.  arXiv preprint arXiv:2305.10601.
  * (79) Yao, W., Heinecke, S., Niebles, J. C., Liu, Z., Feng, Y., Xue, L., Murthy, R., Chen, Z., Zhang, J., Arpit, D., et al. (2023b).  Retroformer: Retrospective large language agents with policy gradient optimization.  arXiv preprint arXiv:2308.02151.
  * Yarotsky, (2017) Yarotsky, D. (2017).  Error bounds for approximations with deep relu networks.  Neural Networks, 94:103–114.
  * Zhang, (2022) Zhang, T. (2022).  Feel-good thompson sampling for contextual bandits and reinforcement learning.  SIAM Journal on Mathematics of Data Science, 4(2):834–857.
  * Zhang, (2023) Zhang, T. (2023).  Mathematical analysis of machine learning algorithms.  Cambridge University Press.
  * Zhang et al., (2022) Zhang, T., Ren, T., Yang, M., Gonzalez, J., Schuurmans, D., and Dai, B. (2022).  Making linear mdps practical via contrastive representation learning.  In International Conference on Machine Learning, pages 26447–26466. PMLR.
  * Zhang et al., (2023) Zhang, Y., Zhang, F., Yang, Z., and Wang, Z. (2023).  What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization.  arXiv preprint arXiv:2305.19420.

Appendix for “From Words to Actions: Unveiling the Theoretical Underpinnings
of LLM-Driven Autonomous Systems”

##  Appendix A Additional Background

In this appendix, we present the additional background knowledge that are
omitted due to the space limit. We first lay out the notations used in this
paper.

#### Notations.

For some $n\in\mathbb{N}^{+}$, let $[n]=\\{1,\dots,n\\}$. Denote
$\Delta(\mathcal{X})$ as the probability simplex over $\mathcal{X}$. Consider
two non-negative sequence $\\{a_{n}\\}_{n\geq 0}$ and $\\{b_{n}\\}_{n\geq 0}$,
if $\limsup a_{n}/b_{n}<\infty$, we write it as $a_{n}=\mathcal{O}(b_{n})$ and
use $\tilde{\mathcal{O}}$ to omit logarithmic terms. Else if $\liminf
a_{n}/b_{n}<\infty$, we write $a_{n}=\Omega(b_{n})$. For continuum
$\mathcal{S}$, denote $|\mathcal{S}|$ as the cardinality. For matrix
$X\in\mathbb{R}^{m\times n}$, the $\ell_{p,q}$-norm is defined as
$\|X\|_{p,q}=(\sum_{i=1}^{n}\|X_{:,i}\|_{p}^{q})^{1/q}$, where $X_{:,i}$
denotes the $i$-th column of $X$.

Table 1: Table of Notations. Notation |  Meaning
---|---
$\mathcal{J}_{z}(\cdot,\cdot)$, $\pi_{z}^{*}(\cdot)$ |  value function and optimal policy $\pi_{z}^{*}(\cdot):=\mathop{\mathrm{argmax}}_{\pi}\mathcal{J}(\pi,\cdot)$ concerning ground-truth $\mathbb{O}$
$\widehat{\mathcal{J}}_{z}(\cdot,\cdot)$, $\widehat{\pi}_{z}^{*}(\cdot)$ |  value function and optimal policy $\widehat{\pi}_{z}^{*}(\cdot):=\mathop{\mathrm{argmax}}_{\pi}\widehat{\mathcal{J}}(\pi,\cdot)$ concerning pretrained $\mathbb{O}_{\widehat{\gamma}}$
$\mathbb{P}_{\mathcal{D}}(\cdot)$, $\mathbb{P}_{\mathcal{C}}(\cdot)$ |  probability induced by the distribution of joint and contrastive data collection
$\pi^{t}_{h,\mathtt{LLM}}$, $\widehat{\pi}^{t}_{h,\mathtt{LLM}}$ |  $\pi^{t}_{h,\mathtt{LLM}}(\cdot\hskip 1.42262pt|\hskip 1.42262pt\tau_{h}^{t},\omega^{t}):=\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})$ and $\widehat{\pi}^{t}_{h,\mathtt{LLM}}(\cdot\hskip 1.42262pt|\hskip 1.42262pt\tau_{h}^{t},\omega^{t}):=\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip 1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})$ at step $h$
$\mathbb{P}_{z}(\cdot)$, $\widehat{\mathbb{P}}_{z}(\cdot)$ |  probability under environment featured by $z$, ground-truth $\mathbb{O}$ or pretrained $\mathbb{O}_{\widehat{\gamma}}$
$\mathbb{P}_{z}^{\pi}(\cdot)$, $\widehat{\mathbb{P}}_{z}^{\pi}(\cdot)$ |  probability under environment featured by $z$, policy $\pi$, ground-truth $\mathbb{O}$ or pretrained $\mathbb{O}_{\widehat{\gamma}}$
$\mathcal{P}_{\Omega}(\cdot)$, $\mathcal{P}_{\mathcal{Z}}(\cdot)$ |  prior distributions of high-level tasks and latent variables
$\breve{\tau}_{h/t}^{i}$ |  $\breve{\tau}_{h/t}^{i}={\tau}_{H}$ for all $i<t$ and $\breve{\tau}_{h/t}^{t}={\tau}_{h}$
$\mathbb{P}_{z}(\cdot|\cdot,\mathrm{\bf do}\hskip 1.70717pt\cdot)$ |  $\mathbb{P}_{z}(\cdot\hskip 1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip 1.70717ptg_{1:h-1}):=\int_{o_{2:h-1}}\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{z}\left(o_{h^{\prime}+1}\hskip 1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}}\right){\mathrm{d}}o_{2:h-1}$
$\mathbb{P}_{\mathtt{LLM}}^{t}(\cdot|\cdot,\mathrm{\bf do}\hskip 1.70717pt\cdot)$ |  $\mathbb{P}_{\mathtt{LLM}}^{t}(\cdot\hskip 1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip 1.70717ptg_{1:h-1}):=\int_{o_{2:h-1}}\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{\mathcal{D}}\left(o_{h^{\prime}+1}\hskip 1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right){\mathrm{d}}o_{2:h-1}$
$\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\cdot,\cdot),\widehat{\pi}_{\mathtt{LLM}}^{t,*}(\cdot)$ |  value function of environment simulated by $\mathtt{LLM}_{\widehat{\theta}}$ and $\widehat{\pi}_{\mathtt{LLM}}^{t,*}(\cdot):=\mathop{\mathrm{argmax}}_{\pi}\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\pi,\cdot)$
$\mathcal{J}_{t,\mathtt{LLM}}(\cdot,\cdot),\pi_{\mathtt{LLM}}^{t,*}(\cdot)$ |  value function of environment simulated by perfect $\mathtt{LLM}$ and ${\pi}_{\mathtt{LLM}}^{t,*}(\cdot):=\mathop{\mathrm{argmax}}_{\pi}\mathcal{{J}}_{t,\mathtt{LLM}}(\pi,\cdot)$
$\mathbb{P}_{\mathtt{LLM}}^{t}(\cdot)$, $\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}(\cdot)$ |  probability of environment simulated by perfect $\mathtt{LLM}$ or pretrained $\mathtt{LLM}_{\widehat{\theta}}$ with $\mathcal{H}_{t}$
$D_{\rm TV}(P,Q)$ |  total variation distance, $D_{\rm TV}(P,Q):=1/2\cdot\mathbb{E}_{x\sim P}[|{\rm d}Q(x)/{\rm d}P(x)-1|]$
$D_{\rm H}^{2}(P,Q)$ |  Helliger distance, $D^{2}_{\rm H}(P,Q):=1/2\cdot\mathbb{E}_{x\sim P}\big{[}\big{(}\sqrt{{\rm d}Q(x)/{\rm d}P(x)}-1\big{)}^{2}\big{]}$
$D_{\rm KL}(P,Q)$ |  KL divergence, $D_{\rm KL}(P\|Q):=\mathbb{E}_{x\sim P}[\log{\mathrm{d}}P(x)/{\mathrm{d}}Q(x)]$
$\chi^{2}(P,Q)$ |  $\chi^{2}$-divergence, $\chi^{2}(P\|Q):=\mathbb{E}_{x\sim P}[({\mathrm{d}}Q(x)/{\mathrm{d}}P(x)-1)^{2}]$
$\widehat{\mathbb{E}}_{\mathcal{D}}[f]$ |  $\bar{\mathbb{E}}[f]:=1/n\cdot\sum_{t=1}^{n}f(\ell_{t})$ given dataset $\mathcal{D}=\\{\ell_{t}\\}_{t\in[n]}$
$\bar{\mathbb{P}}_{\mathcal{D}}(\cdot)$, $\bar{\mathbb{E}}_{\mathcal{D}}[f]$ |  $\bar{\mathbb{P}}_{\mathcal{D}}(\cdot):=\sum_{n=1}^{N}\sum_{t=0}^{T-1}\mathbb{P}_{\mathcal{D}}(\cdot|\ell_{1:t}^{n})/NT$ and $\bar{\mathbb{E}}[f]:=\mathbb{E}_{\ell\sim\bar{\mathbb{P}}_{\mathcal{D}}}[f(\ell)]$ given $\mathcal{D}=\\{\ell_{1:T}^{n}\\}_{n\in[N]}$

###  A.1 Hierarchical Markov Decision Process

In this subsection, we present a formalized definition of the HMDP model
introduced in §3.1.

#### Low-level MDP.

Define $\mathcal{G}$ as the space of high-level actions. For fixed
$g\in\mathcal{G}$ and high-level step $h\in[H]$, the low-level MDP is defined
as
$\mathcal{M}_{h}(g)=(\mathcal{S},\mathcal{A},H_{a},\mathbb{T}_{h},\bar{r}_{g})$,
where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the low-level action
space, $H_{a}$ is the number of steps,
$\mathbb{T}_{h}=\\{\mathbb{T}_{h,\bar{h}}\\}_{\bar{h}\in[H_{a}]}$ is the
transition kernel, and $\bar{r}=\\{\bar{r}_{\bar{h}}\\}_{\bar{h}\in[H_{a}]}$
is the reward function with
$\bar{r}_{\bar{h}}:{\mathcal{S}}\times\mathcal{A}\times\mathcal{G}\mapsto\mathbb{R}$.
The low-level agent follows policy $\mu=\\{\mu_{g}\\}_{g\in\mathcal{G}}$,
where $\mu_{g}=\\{\mu_{\bar{h}}\\}_{\bar{h}\in[H_{a}]}$ and
$\mu_{\bar{h}}:{\mathcal{S}}\times\mathcal{G}\mapsto\Delta(\mathcal{A})$.

#### High-level POMDP.

Define $\Omega$ be the space of disclosed variables, and we write
$z=(\mathbb{T},\mu)$ to feature the low-level environment. Each low-level
episode corresponds to a single high-level action. Given fixed pair
$(z,\omega)\in\mathcal{Z}\times\Omega$, the POMDP is characterized by
$\mathcal{W}(z,\omega)=(\mathcal{S},\mathcal{O},\mathcal{G},H,\mathbb{P}_{z},r_{\omega})$,
where $\mathcal{O}$ is the observation space,
$\mathbb{O}=\\{\mathbb{O}_{h}\\}_{h\in[H]}$ is the emission distribution with
$\mathbb{O}_{h}:\mathcal{O}\mapsto\Delta({\mathcal{S}})$,
$r=\\{r_{h}\\}_{h\in[H]}$ is the reward function with
$r_{h}:\mathcal{O}\times\Omega\mapsto\mathbb{R}$, and
$\mathbb{P}_{z}=\\{\mathbb{P}_{z,h}\\}_{h\in[H]}$ is the high-level transition
kernel following that

$\displaystyle\mathbb{P}_{z,h}(s^{\prime}\hskip 1.42262pt|\hskip
1.42262pts,g)=\mathbb{P}\big{(}\bar{s}_{h,H_{a}+1}=s^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\bar{s}_{h,1}=s,a_{h,1:\bar{h}}\sim\mu_{g},\bar{s}_{h,2:\bar{h}+1}\sim\mathbb{T}_{h}\big{)},$

for all $h\in[H]$. The space of state $\mathcal{S}$ and latent variable $z$
are inherited from the low-level MDP.

Please refer to Figure 2 for the interactive protocol of HMDP. Furthermore,
for the high-level POMDP, the state value function of policy $\pi$, the state
value function is defined as

$V_{z,h}^{\pi}(s,\tau,\omega)=\mathbb{E}_{\pi}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(o_{h^{\prime}},\omega)\Big{|}s_{h}=s,\tau_{h}=\tau\right],$
(A.1)

where trajectory
$\tau_{h}\in(\mathcal{O}\times\mathcal{G})^{h-1}\times\mathcal{O}$, and
similarly we define the state-action value function as

$Q_{z,h}^{\pi}(s,\tau,g,\omega)=\mathbb{E}_{\pi}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(o_{h^{\prime}},\omega)\Big{|}s_{h}=s,\tau_{h}=\tau,g_{h}=g\right],$
(A.2)

where expectation is taken concerning the policy $\pi$, transition kernel
$\mathbb{P}_{z}$, and emission distribution $\mathbb{O}$. Besides, for all
$h\in[H]$, denote the probability of observing trajectory $\tau_{h}$ under
policy $\pi$ as

$\displaystyle\mathbb{P}_{z}^{\pi}(\tau_{h})=\pi(\tau_{h})\cdot\mathbb{P}_{z}(\tau_{h}),\quad\mathbb{P}_{z}(\tau_{h})=\prod_{h^{\prime}=1}^{h-1}\mathbb{P}(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h^{\prime}},g_{h^{\prime}}),\quad\pi(\tau_{h})=\prod_{h^{\prime}=1}^{h-1}\pi_{h}(g_{h^{\prime}}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h^{\prime}}),$ (A.3)

where $\mathbb{P}_{z}(\tau_{h})$ denotes the part of the probability of
$\tau_{h}$ that is incurred by the dynamic environment independent of
policies, $\pi(\tau_{h})$ denotes the part that can be attributed to the
randomness of policy.

###  A.2 LLM Pretraining under Transformer Architecture

#### Transformer and Attention Mechanism.

Consider a sequence of $N$ input vectors
$\\{\mathbf{h}_{i}\\}_{i=1}^{n}\subset\mathbb{R}^{d}$, written as an input
matrix
$\mathbf{H}=[\mathbf{h}_{1},\dots,\mathbf{h}_{n}]^{\top}\in\mathbb{R}^{n\times
d}$, where each $\mathbf{h}_{i}$ is a row of $\mathbf{H}$ (also a token).
Consider $\mathbf{K}\in\mathbb{R}^{n_{s}\times d}$ and
$\mathbf{V}\in\mathbb{R}^{n_{s}\times d_{s}}$, then the (softmax) attention
mechanism maps these input vectors using the function
$\mathtt{attn}(\mathbf{H},\mathbf{K},\mathbf{V})=\mathtt{Softmax}(\mathbf{H}\mathbf{K}^{\top})\mathbf{V}\in\mathbb{R}^{n\times
d_{s}}$, where softmax function is applied row-wisely and normalize each
vector via the exponential function such that
$[\mathtt{Softmax}(\mathbf{h})]_{i}=\exp(\mathbf{h}_{i})/\sum_{j=1}^{d}\exp(\mathbf{h}_{j})$
for all $i\in[d]$. To approximate sophisticated functions, practitioners use
Multi-head Attention (MHA) instead, which forwards the input vectors into $h$
attention modules in parallel with $h\in\mathbb{N}$ as a hyperparameter and
outputs the sum of these sub-modules. Denote
$\mathbf{W}=\\{(\mathbf{W}^{H}_{i},\mathbf{W}^{K}_{i},\mathbf{W}^{V}_{i})\\}_{i=1}^{h}$
as the set of weight matrices, the MHA outputs
$\mathtt{Mha}(\mathbf{H},\mathbf{W})=\sum_{i=1}^{h}\mathtt{attn}(\mathbf{H}\mathbf{W}^{H}_{i},\mathbf{H}\mathbf{W}^{K}_{i},\mathbf{H}\mathbf{W}^{V}_{i})$,
where $\mathbf{W}^{H}_{i}\in\mathbb{R}^{d\times d_{h}}$,
$\mathbf{W}^{K}_{i}\in\mathbb{R}^{d\times d_{h}}$ and
$\mathbf{W}^{V}_{i}\in\mathbb{R}^{d\times d}$ for all $i\in[h]$, and $d_{h}$
is usually set to $d/h$ (Michel et al.,, 2019). Based on the definitions
above, we are ready to present the transformer architecture employed in LLMs
like BERT and GPT (Devlin et al.,, 2018; Brown et al.,, 2020). Detailedly, the
transformer network has $D$ sub-modules, consisting of an MHA and Feed-Forward
(FF) fully-connected layer. Given input matrix
$\mathbf{H}^{(0)}=\mathbf{H}\in\mathbb{R}^{n\times d}$, in the $j$-th layer
for $j\in[D]$, it first takes the output from the $(t-1)$-th layer
$\mathbf{H}^{(t-1)}$ as the input matrix, and forwards it to the MHA module
with a projection function $\mathtt{Proj}[\cdot]$ and a residual link. After
receiving intermediate $\overline{\mathbf{H}}^{(t)}\in\mathbb{R}^{n\times d}$,
the FF module maps each row through a same single-hidden layer neural network
with $d_{F}$ neurons such that
$\mathtt{ReLU}(\overline{\mathbf{H}}^{(t)}\mathbf{A}_{1}^{(t)})\mathbf{A}_{2}^{(t)}$,
where $\mathbf{A}_{1}^{(t)}\in\mathbb{R}^{d\times d_{F}}$,
$\mathbf{A}_{2}^{(t)}\in\mathbb{R}^{d_{F}\times d}$, and
$[\mathtt{ReLU}(\mathbf{X})]_{i,j}=\max\\{\mathbf{X}_{i,j},0\\}$.
Specifically, the output of the $t$-th layer with $t\in[D]$ can be summarized
as below:

$\displaystyle\overline{\mathbf{H}}^{(t)}=\mathtt{Proj}\left[\mathtt{Mha}\left({\mathbf{H}}^{(t-1)},\mathbf{W}^{(t)}\right)+\gamma_{1}^{(t)}{\mathbf{H}}^{(t-1)}\right],\quad{\mathbf{H}}^{(t)}=\mathtt{Proj}\left[\mathtt{ReLU}(\overline{\mathbf{H}}^{(t)}\mathbf{A}_{1}^{(t)})\mathbf{A}_{2}^{(t)}+\gamma_{2}^{(t)}\overline{\mathbf{H}}^{(t)}\right],$

where $\gamma_{1}^{(t)}$ and $\gamma_{2}^{(t)}$ features the allocation of
residual link. The final output of the transformer is the probability of the
next token via a softmax distribution such that

${\mathbf{H}}^{(D+1)}=\mathtt{Softmax}\left(\mathbf{1}^{\top}{\mathbf{H}}^{(D)}\mathbf{A}^{(D+1)}/N\gamma^{(D+1)}\right),$

where $\mathbf{A}^{(D+1)}\in\mathbb{R}^{d\times d_{E}}$ denotes the weight
matrix with dimension $d_{E}\in\mathbb{N}$ and $\gamma^{(D+1)}\in(0,1]$ is the
fixed temperature parameter. Let
$\bm{\theta}^{(t)}=\left(\mathbf{W}^{(t)},\mathbf{A}^{(t)},\bm{\gamma}^{(t)}\right)$
for all $t\in[D]$, where
$\mathbf{A}^{(t)}=(\mathbf{A}^{(t)}_{1},\mathbf{A}^{(t)}_{2})$ and
$\bm{\gamma}^{(t)}=(\gamma_{1}^{(t)},\gamma_{2}^{(t)})$, and denote
$\bm{\theta}^{(D+1)}=(\mathbf{A}^{(D+1)},\gamma)$. Hence, the parameter of the
whole transformer architecture is the concatenation of parameters in each
layer such that $\bm{\theta}=(\bm{\theta}^{(1)},\dots,\bm{\theta}^{(D+1)})$,
and we consider a bounded parameter space, which is defined as below

$\displaystyle\bm{\Theta}:=\\{\bm{\theta}\hskip 1.42262pt|\hskip 1.42262pt$
$\displaystyle\|\mathbf{A}^{(t)}_{1}\|_{F}\leq
B_{A,1},\|\mathbf{A}^{(t)}_{2}\|_{F}\leq
B_{A,2},\|\mathbf{A}^{(D+1),\top}\|_{1,2}\leq B_{A},|\gamma_{1}^{(t)}|\leq
1,|\gamma_{2}^{(t)}|\leq 1,$ $\displaystyle|\gamma^{(D+1)}|\leq
1,\|\mathbf{W}_{i}^{H,(t)}\|\leq B_{H},\|\mathbf{W}_{i}^{K,(t)}\|\leq
B_{K},\|\mathbf{W}_{i}^{V,(t)}\|\leq B_{V},\forall(i,t)\in[h]\times[D]\\}.$

To facilitate the expression of Theorem 2, we further define
$\bar{D}=D^{2}d\cdot(d_{h}+d_{F}+d)+d_{E}\cdot d$ and
$\bar{B}=\gamma^{-1}RhB_{A,1}B_{A,2}B_{A}B_{H}B_{K}B_{V}$, where $R$ is
(almost surely) the upper bound of the magnitude of each token
$\ell\in\mathfrak{L}$ in token sequence $S_{t}\in\mathfrak{L}^{*}$, which is
defined in Assumption 5.1.

#### Markov Chains.

We follow the notations used in Paulin, (2015); Zhang et al., (2023). Let
$\Omega$ be a Polish space. The transition kernel for a time-homogeneous
Markov chain $\\{X_{i}\\}_{i=1}^{\infty}$ supported on $\Omega$ is a
probability distribution $\mathbb{P}(x,y)$ for every $x\in\Omega$. Given
$X_{1}=x_{1},\cdots,X_{t-1}=x_{t-1}$, the conditional distribution of $X_{t}$
equals $\mathbb{P}(x_{t-1},y)$. A distribution $\pi$ is said to be a
stationary distribution of this Markov chain if
$\int_{x\in\Omega}\mathbb{P}(x,y)\cdot\pi(x)=\pi(y)$. We adopt
$\mathbb{P}_{t}(x,\cdot)$ to denote the distribution of $X_{t}$ conditioned on
$X_{1}=x$. The mixing time of the chain is defined by

$\displaystyle d(t)=\sup_{x\in\Omega}D_{\rm
TV}\big{(}\mathbb{P}_{t}(x,\cdot),\pi\big{)},\quad t_{\rm
mix}(\varepsilon)=\min\\{t\hskip 1.42262pt|\hskip
1.42262ptd(t)\leq\varepsilon\\},\quad t_{\rm mix}=t_{\rm mix}(1/4).$ (A.4)

##  Appendix B Extentions

###  B.1 LLM Planning via Bayesian Aggregated World Model

Algorithm 2 Planning with PAR System - Planner with LLM as World Model

1:Policy $\pi_{\mathtt{exp}}$ with $\eta\in(0,1)$, parameter
$c_{\mathcal{Z}}>0$, $N_{\rm s}\in\mathbb{N}$, and
$|\mathcal{Z}|\in\mathbb{N}$,

2: and reward function $r=\\{r_{h}\\}_{h\in[H]}$ specified by the human user.

3:$\mathcal{H}_{0}\leftarrow\\{\\}$, $\mathcal{D}_{t}^{\rm
s}\leftarrow\\{\\},\forall t\in[T]$, and
$\epsilon\leftarrow(\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})/T\eta)^{1/2}$.

4:for episode $t$ from $1$ to $T$ do

5: Receive the high-level task $\omega^{t}$ from the human user.

6: Sample $\mathcal{I}_{t}\sim\text{Bernuolli}(\epsilon)$.

7: for stimulation $n$ from 1 to $N_{\rm s}$ do

8: Sample $g_{h,n}^{t,{\rm s}}\sim{\rm Unif}(\mathcal{G})$ for all $h\in[H]$
and set
$\mathtt{pt}_{1,n}^{t}\leftarrow\mathcal{H}_{t}\cup\\{o_{1}^{t},g_{1,n}^{t,{\rm
s}}\\}$.

9: for step $h$ from $1$ to $H$ do

10: Update
$\mathtt{pt}_{h,n}^{t}\leftarrow\mathcal{H}_{t}\cup\big{\\{}o_{1,n}^{t},g_{1,n}^{t,{\rm
s}},\dots,o_{h,n}^{t,{\rm s}},g_{h,n}^{t,{\rm s}}\big{\\}}$.

11: Predict $o_{h+1,n}^{t,{\rm s}}\sim\mathtt{LLM}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h,n}^{t})$ via prompting LLM.

12: end for

13: Update $\mathcal{D}_{t}^{\rm s}\leftarrow\mathcal{D}_{t}^{\rm
s}\cup\big{\\{}o_{1,n}^{t},g_{1,n}^{t,{\rm s}},\dots,o_{H-1,n}^{t,{\rm
s}},g_{H-1,n}^{t,{\rm s}},o_{H,n}^{t,{\rm s}}\big{\\}}$.

14: end for

15: for step $h$ from $1$ to $H$ do

16: Collect the observation $o_{h}^{t}$ from the Reporter.

17: Calculate $\pi_{\texttt{LLM}}^{t}\leftarrow\textsc{Optimal-
planning}(\omega^{t},\mathcal{D}_{t}^{\rm s},r)$

18: Sample
$g_{h}^{t}\sim(1-\mathcal{I}_{t})\cdot\pi_{h,\texttt{LLM}}^{t}(\cdot\hskip
1.42262pt|\hskip
1.42262pt\omega^{t},\tau_{h}^{t})+\mathcal{I}_{t}\cdot\pi_{h,\mathtt{exp}}^{t}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\tau_{h}^{t})$.

19: Send the subgoal $g_{h}^{t}$ to the Actor.

20: end for

21: Update
$\mathcal{H}_{t+1}\leftarrow\mathcal{H}_{t}\cup\left\\{\omega^{t},\tau_{H}^{t}\right\\}$.

22:end for

Recall that the pretraining algorithm in §3.2 also equips LLM with the
capability to predict observation generation, i.e.,
$\mathbb{P}_{h}(o_{h}\hskip 1.42262pt|\hskip 1.42262pt(o,g)_{1:h-1})$.
Existing literature has shown the benefits of augmenting the reasoning process
with predicted world states, as it endows LLMs with a more grounded inference
without reliance on expert knowledge (Hu and Shu,, 2023). Specifically, the
Planner interactively prompts LLM to internally simulate entire trajectories
grounded on historical feedback. By leveraging model-based RL methods such as
Monte Carlo Tree Search (Browne et al.,, 2012) and Real-Time Dynamic
Programming (Barto et al.,, 1995), the Planner utilizes the LLM-simulated
environment to optimize its strategies. The planning protocol is as follows:
at the beginning of $t$-th episode, Planner iteratively prompts LLM with
initial observation $o_{1}$, history $\mathcal{H}_{t}$, and subgoals $g_{1:H}$
sequentially to predict observations $o_{1:H}$. Subsequently, a simulation
dataset $\mathcal{D}_{t}^{\rm s}$ is collected, allowing the Planner to
compute the optimal policy with rewards specified by the human users, using
methods such as MCTS. We first show that the LLM-simulated environment
conforms to a Bayesian Aggregated World Model (BAWM), and is formalized as
follows.

######  Proposition B.1 (LLM as BAWM).

Assume that the distribution of pretraining data is given by (3.5). Under the
perfect setting in Definition 4.1, for each $(h,t)\in[H]\times[T]$, the LLM
serves as a Bayesian aggregated world model, following that

$\displaystyle\mathbb{P}_{\mathtt{LLM}}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1})=\sum_{z\in\mathcal{Z}}\mathbb{P}_{z}\left(\cdot\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t}\right),$ (B.1)

with marginal distributions defined as $\mathbb{P}_{z}(\cdot\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1})=\int_{o_{2:h-1}}\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{z}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}}\right){\mathrm{d}}o_{2:h-1}$
and $\mathbb{P}_{\mathtt{LLM}}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1})=\int_{o_{2:h-1}}\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{\mathcal{D}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right){\mathrm{d}}o_{2:h-1}$.

###### Proof of Propoition B.1..

Please refer to §E.1 for a detailed proof. ∎

Note that the generation distribution
$\mathbb{P}_{\mathtt{LLM}}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pt(o,g)_{1:h})=\texttt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt(o,g)_{1:h},\mathcal{H}_{t})$ is non-stationary, since
$\mathbb{P}_{\mathcal{D}}(z\hskip 1.42262pt|\hskip
1.42262pt(o,g)_{1:h},\mathcal{H}_{t})$ fluctuates with simulated part
$(o,g)_{1:h}$ due to the autoregressive manner of LLMs. Instead, Proposition
B.1 posits that the marginal distribution has a stationary expression based on
posterior aggregation. Akin to Assumption 5.6, we introduce the coverage
assumption.

######  Assumption B.2 (Strong Coverage).

There exists absolute constants $\lambda_{S,1},\lambda_{S,2}$ and
$\lambda_{R}$ such that for all $z\in\mathcal{Z}$, length $t<\bar{T}_{\rm p}$
and policy sequence $\\{\pi^{i}\\}_{i\leq\lfloor t/2H\rfloor}$ from the
Planner, it holds that (i) $\prod_{i=1}^{\lfloor
t/2H\rfloor}\mathbb{\widehat{P}}_{z}^{\pi_{i}}(\tilde{S}_{i})\leq\lambda_{S,1}\cdot\bar{\mathbb{P}}_{\mathcal{D}_{\mathtt{LLM}}}((\tilde{S}_{i})_{i\leq\lfloor
t/2H\rfloor})$ and
$\bar{\mathbb{P}}_{\mathcal{D}_{\mathtt{LLM}}}(\tilde{S}_{\lceil
t/2H\rceil}|(\tilde{S}_{i})_{i\leq\lfloor t/2H\rfloor})\geq\lambda_{S,2}$ for
all ordered $S_{t}=(\tilde{S}_{i})_{i\leq\lceil
t/2H\rceil}\in\mathfrak{L}^{*}$, where $|\tilde{S}_{i}|=2H$ for all $k<\lceil
t/2H\rceil$, (ii)
$\bar{\mathbb{P}}_{\mathcal{D}_{\mathtt{Rep}}}(s)\geq\lambda_{R}$ for all
$s\in\mathcal{S}$.

We remark that Assumption B.2 imposes a stronger condition over the coverage,
particularly on the in-episode trajectory $\tilde{S}_{\lceil t/2H\rceil}$,
Here, $\lceil t/2H\rceil$ denotes the number of episodes described in $S_{t}$.
The demand of the stronger assumption arises from LLM now serving as a WM,
necessitating more extensive information across all kinds of scenarios.
Suppose that the Planner can learn optimal policy
$\widehat{\pi}^{t,*}_{\mathtt{LLM}}={\rm argmax}_{\pi\in\Pi}\
\mathcal{\widehat{J}}_{\mathtt{LLM}}^{t}(\pi,\omega)$ with sufficiently large
simulation steps $|\mathcal{D}_{t}^{\rm s}|$, where
$\mathcal{\widehat{J}}_{\mathtt{LLM}}^{t}$ denotes the value function
concerning $\mathtt{LLM}_{\widehat{\theta}}$ and history $\mathcal{H}_{t}$.
Akin to Algorithm 1, the planning algorithm by taking LLM as WM includes an
$\epsilon$-greedy exploration with $\eta$-distinguishable
$\pi_{\mathtt{exp}}$. The pseudocode is in Algorithm 2. The following
corollary presents the performance under practical settings.

######  Corollary B.3 (Regret under Practical Setting with LLM as World
Model).

Suppose that Assumptions 4.5, 5.1, 5.2, 5.4 and 5.6. Given an
$\eta$-distinguishable exploration policy $\pi_{\mathtt{exp}}$ and $T\leq
T_{\rm p}$, under the practical setting, the Planner’s algorithm in Algorithm
2 ensures that

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\tilde{\mathcal{O}}\Big{(}H\sqrt{T/\eta\cdot\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})}+H^{2}T\cdot\Delta_{\rm
p,wm}(N_{\rm p},T_{\rm p},H,1/\sqrt{T},\xi)\Big{)},$

for any $z\in\mathcal{Z}$ and $\\{\omega_{t}\\}_{t\in[T]}$. The cumulative
pretraining error of the PAR system follows

$\displaystyle\Delta_{\rm p,wm}(N_{\rm p},T_{\rm
p},H,\delta,\xi)=2(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}$
$\displaystyle\quad+2\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)+2\lambda_{S,1}\lambda_{S,2}^{-1}\cdot\Delta_{\mathtt{LLM}}(N_{\rm
p},T_{\rm p},H,\delta).$

where $\xi=(\eta,\lambda_{S,1},\lambda_{S,2},\lambda_{R})$ are defined in
Definition 4.4 and Assumption 5.6, and errors $\Delta_{\mathtt{LLM}}$ and
$\Delta_{\mathtt{Rep}}$ are defined in Theorem 2 and Theorem 5.5. Under
practical setting, Planner should explore with probability
$\epsilon=(\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})/T\eta)^{1/2}+H(\eta\lambda_{\min})^{-1}\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,1/\sqrt{T})^{2}$.

###### Proof of Corollary B.3..

Please refer to §E.2 for a detailed proof. ∎

###  B.2 LLM-Empowered Multi-Agent Collaboration

Algorithm 3 Multi-Agent Planning with PAR System - Planner

1:Policy $\pi_{\mathtt{exp}}$ with $\eta\in(0,1)$, parameter
$c_{\mathcal{Z}}>0$, and $|\mathcal{Z}|\in\mathbb{N}$.

2:$\mathcal{H}_{0}\leftarrow\emptyset$, and
$\epsilon\leftarrow(HK\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})/T\eta)^{1/2}$.

3:for episode $t$ from $1$ to $T$ do

4: Receive the high-level task $\omega^{t}$ from the human user.

5: Sample $\mathcal{I}_{t}\sim\text{Bernuolli}(\epsilon)$.

6: for step $h$ from $1$ to $H$ do

7: Collect the observation $o_{h}^{t}$ from Reporter.

8: for Actor $k$ from $1$ to $K$ do

9: Set
$\mathtt{pt}_{h,k}^{t}\leftarrow\mathcal{H}_{t}\cup\left\\{\omega^{t},o_{1}^{t},g_{1}^{t},\dots,o_{h}^{t},k\right\\}$.

10: Sample $g_{h,k,\mathtt{LLM}}^{t}\sim\mathtt{LLM}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h,k}^{t})$ via prompting LLM.

11: end for

12: If $\mathcal{I}_{t}=1$ then $g_{h}^{t}\leftarrow g_{h,\mathtt{LLM}}^{t}$,
else sample $g_{h}^{t}\sim\pi_{h,\mathtt{exp}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t})$.

13: end for

14: Send the subgoal $g_{h}^{t}$ to the Actors.

15: Update
$\mathcal{H}_{t+1}\leftarrow\mathcal{H}_{t}\cup\left\\{\omega^{t},\tau_{H}^{t}\right\\}$.

16:end for

To characterize the multi-agent interactive process, i.e., several Actors, of
task planning, we consider a turn-based _cooperative_ hierarchical Markov Game
(HMG), corresponding to HMDP in §3.1. Instead, HMG consists of a low-level
language-conditioned Markov Game (MG) and a high-level language-conditioned
cooperative Partially Observable Markov Game (POMG). To extend this framework,
we introduce the following modifications: (i) low-level MG: let
$\mathcal{K}=[K]$ be the set of Actors, and
$\mathcal{G}=\mathcal{G}_{1}\times\dots\times\mathcal{G}_{K}$ and
$\mathcal{A}=\mathcal{A}_{1}\times\dots\times\mathcal{A}_{K}$ be the space of
subgoals and low-level actions. Low-level Actors conduct planning following a
joint policy $\mu=\\{\mu_{h}\\}_{h\in[H]}$ with
$\mu_{h}:\mathcal{S}\times\mathcal{G}\mapsto\Delta(\mathcal{A})$, where
$\\{\mu_{h,k}\\}_{k\in\mathcal{K}}$ can be correlated, e.g., within zero-sum
game, Stackelberg game (Başar and Olsder,, 1998). (ii) high-level POMG: under
cooperation, assume that policies can be factorized as

$\pi_{h}(\mathbf{g}_{h}\hskip 1.42262pt|\hskip
1.42262pt\tau_{h-1},\omega)=\prod_{k=1}^{K}\pi_{h,k}(g_{h,k}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h-1},\omega),\quad\forall h\in[H].$

The remaining concepts are consistent with HMDP. Here, the Planner assumes the
role of _central controller_ and solves a fully-cooperative POMG that aims to
maximize a shared value function. Thus, the Planner should infer both the
Actors’ intentions, i.e., joint policy $\mu$, and the environment, i.e.,
transition kernel $\mathbb{T}$, from the historical context, and then assign
subgoal for each Actor.

Specifically, the LLM’s recommendations are obtained by invoking the ICL
ability of LLMs with the history-dependent prompt akin to (3.2) sequentially
for each Actor. For the $k$-th Actor, prompt LLM with
$\mathtt{pt}_{h,k}^{t}=\mathcal{H}_{t}\cup\\{\omega^{t},\tau_{h}^{t},k\\}$,
where denote
$\mathcal{H}_{t}=\bigcup_{i=1}^{t-1}\\{\omega^{i},\tau_{H}^{i}\\}$ and
$\tau_{h}^{t}=\\{o_{h}^{1},\mathbf{g}_{h}^{1},\dots,o_{h}^{t}\\}$. Under the
perfect setting (see Definition 4.1), LLM’s joint policy for recommendations
follows:

$\displaystyle\pi_{h,\mathtt{LLM}}^{t}\big{(}\mathbf{g}_{h}^{t}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h}^{t},\omega^{t}\big{)}$
$\displaystyle=\prod_{k\in\mathcal{K}}\left(\sum_{z\in\mathcal{Z}}\pi^{*}_{z,h,k}\left(g_{h,k}^{t}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right)\right),$ (B.2)

which is akin to Proposition 4.2 and the proof of the statement is provided in
§E.3. The pseudocode is presented in Algorithm 3. Then, we give the
performance guarantee under multi-agent scenarios with the perfect PAR system.

######  Corollary B.4 (Multi-agent Collaboration Regret under Perfect
Setting).

Suppose that Assumptions 4.1 and 4.5 hold. Given an $\eta$-distinguishable
exploration policy $\pi_{\mathtt{exp}}$ and $T\leq T_{\rm p}$, the Planner’s
algorithm in Algorithm 3 guarantees that

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\tilde{\mathcal{O}}\left(H^{\frac{3}{2}}\sqrt{TK/\eta\cdot\log\left(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T}\right)}\right),$

for any $z\in\mathcal{Z}$ and $\\{\omega^{t}\\}_{t\in[T]}$, if Planner
explores with
$\epsilon=(HK\log\left(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T}\right)/T\eta)^{1/2}$.

###### Proof of Corollary B.4..

Please refer to §E.3 for a detailed proof. ∎

Corollary B.4 is akin to Theorem 4.6 with an additional $\sqrt{K}$ in regret.
Besides, the multi-agent space of latent variable
$|\mathcal{Z}|=|\mathcal{Z}_{\mathbb{T}}|\times|\mathcal{Z}_{\mu,\rm m}|$,
where $\mathcal{Z}_{\mu,\rm m}$ is the space of joint policy, is generally
larger than the single-agent space. Specifically, if responses are
uncorrelated, then we have $\log|\mathcal{Z}_{\mu,\rm
m}|=K\log|\mathcal{Z}_{\mu,\rm s}|$, resulting in a $\sqrt{K}$ times larger
regret. The proof of extension to practical setting is akin to Corollary B.4
based on derivations in Theorem 5.7, and is omitted.

##  Appendix C Proof for Section 4: Perfect Setting

###  C.1 Proof of Proposition 4.2

_Proof of Proposition 4.2._ Note that for all $h\in[H]$ and $t\in[T]$, we have

$\displaystyle\pi_{h,\mathtt{LLM}}^{t}\left(g_{h}^{t}\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)$
$\displaystyle=\sum_{z\in\mathcal{Z}}\mathbb{P}_{\mathcal{D}}\left(g_{h}^{t}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t},z\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right)$
$\displaystyle=\sum_{z\in\mathcal{Z}}\mathbb{P}_{\mathcal{D}}\left(g_{h}^{t}\hskip
1.42262pt|\hskip
1.42262pt\mathcal{H}_{t},\tau_{h}^{t},\omega^{t},z\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right)$
$\displaystyle=\sum_{z\in\mathcal{Z}}\pi^{*}_{z,h}\left(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right),$ (C.1)

where the second equation results from the law of total probability, the third
equation follows the definition of prompts in (3.2), and the last equation
results from the generation distribution. $\Box$

###  C.2 Proof of Theorem 4.6

_Proof of Thereom 4.6._ Recall that the Planner takes a mixture policy of
$\pi_{\mathtt{exp}}$ and $\pi_{\mathtt{LLM}}$ such that

$\pi_{h}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})\sim(1-\epsilon)\cdot\pi_{h,\mathtt{LLM}}^{t}(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})+\epsilon\cdot\pi_{h,\mathtt{exp}}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\tau_{h}^{t}),$ (C.2)

and Proposition 4.2 indicates that LLM’s recommended policies take the form:

$\displaystyle\pi_{h,\mathtt{LLM}}^{t}\left(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)=\sum_{z\in\mathcal{Z}}\pi^{*}_{z,h}\left(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}\right),\text{~{}where~{}}\mathtt{pt}_{h}^{t}=\mathcal{H}_{t}\cup\tau_{h}^{t},\mathcal{H}_{t}=\left\\{\omega^{i},\tau_{H}^{i}\right\\}_{i\in[t-1]},$
(C.3)

for all $(h,t)\in[H]\times[T]$. Following (C.2), given $z\in\mathcal{Z}$ and
$\\{\omega^{t}\\}_{t\in[T]}$, the regret is decomposed as

$\displaystyle\text{Reg}(T)$
$\displaystyle=\underbrace{\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-\pi_{h,\mathtt{exp}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]\cdot\epsilon}_{\textbf{(i)}}$
$\displaystyle\hskip
11.38092pt+\underbrace{\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]\cdot(1-\epsilon)}_{\textbf{(ii)}}$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]+HT\epsilon,$
(C.4)

where the second equation results from performance difference lemma (PDL, see
Lemma F.4), and we write
$\pi_{h}Q_{h}(s_{h},\tau_{h},\omega)=\langle\pi_{h}(\cdot|\tau_{h},\omega),Q_{h}(s_{h},\tau_{h},\cdot,\omega)\rangle_{\mathcal{G}}$,
and $\mathbb{P}_{z}^{\pi}(\tau_{h})$ is defined in (A.3). Based on Lemma C.1,
with probability at least $1-\delta$, the following event $\mathcal{E}_{1}$
holds: for all $(h,t)\in[H]\times[T]$,

$\sum_{z^{\prime}\in\mathcal{Z}}\sum_{i\in[t]}D_{\rm
H}^{2}\big{(}\mathbb{P}_{z}^{\pi^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z^{\prime}}^{\pi^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})\leq
2\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right),$ (C.5)

where the randomness is incurred by $\mathtt{pt}_{h}^{t}$ and define
$\breve{\tau}_{h/t}^{i}={\tau}_{H}$ for all $i\in[t-1]$ and
$\breve{\tau}_{h/t}^{t}={\tau}_{h}$ for notational simplicity. Suppose that
event $\mathcal{E}_{1}$ in (C.5) holds, and denote
$\mathcal{X}^{t}_{\mathtt{exp}}=\\{i\in[t]:\pi^{i}=\pi_{\mathtt{exp}}\\}$ as
the set of exploration episodes. Note that for all
$(h,t,z^{\prime})\in[H]\times[T]\times\mathcal{Z}$, it holds that

$\displaystyle\sum_{i\in[t]}D_{\rm
H}^{2}\big{(}\mathbb{P}_{z}^{\pi^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z^{\prime}}^{\pi^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\geq\sum_{i\in\mathcal{X}^{t-1}_{\mathtt{exp}}}D_{\rm
H}^{2}\left(\mathbb{P}_{z}^{\pi_{\mathtt{exp}}}({\tau}_{H}),\mathbb{P}_{z^{\prime}}^{\pi_{\mathtt{exp}}}({\tau}_{H})\right)\geq{\eta\cdot|\mathcal{X}^{t-1}_{\mathtt{exp}}|},$
(C.6)

where the last inequality results from $\pi_{\mathtt{exp}}$ is
$\eta$-distinguishable (see Definition 4.4) and the fact that $D_{\rm
H}^{2}(P,Q)\leq 1$ for all $P,Q\in\Delta(\mathcal{X})$. Combine (C.5) and
(C.6), we can get

$\sum_{z^{\prime}\neq z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\leq\min\left\\{2\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)\eta^{-1}/|\mathcal{X}^{t-1}_{\mathtt{exp}}|,1\right\\},$
(C.7)

for all $(h,t)\in[H]\times[T]$. Recall that (C.3) indicates that for all
$(h,t)\in[H]\times[T]$, we have

$\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)(\cdot\hskip
1.42262pt|\hskip 1.42262pt\tau_{h},\omega)=\sum_{z^{\prime}\neq
z}\left(\pi_{z,h}^{*}-\pi_{z^{\prime},h}^{*}\right)(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h},\omega)\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}).$

Based on Proposition 4.2 and conditioned on $\mathcal{E}_{1}$, it holds that

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]$
$\displaystyle\leq H\cdot\sum_{t=1}^{T}\sum_{h=1}^{H}\sum_{z^{\prime}\neq
z}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{P}_{z}^{\pi^{t}}}\Biggl{[}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})\Biggl{]}$ $\displaystyle\leq
2\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)H\eta^{-1}\cdot\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}\left[\min\left\\{1/|\mathcal{X}^{t-1}_{\mathtt{exp}}|,1\right\\}\right],$
(C.8)

Note that $\mathds{1}(\pi^{t}=\pi_{\mathtt{exp}})\overset{\rm
iid}{\sim}\text{Bernuolli}(\epsilon)$ for all $t\in[T]$. Besides,the following
event $\mathcal{E}_{2}$ holds:

$\displaystyle\sum_{t=1}^{T}\min\left\\{1/|\mathcal{X}^{t-1}_{\mathtt{exp}}|,1\right\\}\leq\mathcal{O}(\epsilon^{-1}\log(T\log
T/\delta)).$ (C.9)

with probability at least $1-\delta$ based on Lemma F.5. Combine (C.4), (C.8)
and (C.9), we have

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h},\tau_{h},\omega^{t})\operatorname{\mathds{1}}\left(\mathcal{E}_{1}\cap\mathcal{E}_{2}\text{~{}holds}\right)\right]$
$\displaystyle\quad+\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h},\tau_{h},\omega^{t})\operatorname{\mathds{1}}\left(\mathcal{E}_{1}\cap\mathcal{E}_{2}\text{~{}fails}\right)\right]+HT\epsilon$
$\displaystyle\leq\mathcal{O}\Big{(}\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)H^{2}\log(T\log
T/\delta)\cdot(\eta\epsilon)^{-1}+HT\epsilon+2HT\delta\Big{)}$
$\displaystyle\leq\tilde{\mathcal{O}}\left(H^{\frac{3}{2}}\sqrt{\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)T/\eta}\right),$

where we choose to expolre with probability
$\epsilon=(H\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)/T\eta)^{1/2}$.
If we take $\delta=1/\sqrt{T}$ in the arguments above, then we can conclude
the proof of Theorem 4.6. $\Box$

###  C.3 Proof of Lemma C.1

######  Lemma C.1.

Suppose that Assumptions 4.1 and 4.5 hold. Given $\delta\in(0,1)$ and ground-
truth $z\in\mathcal{Z}$, for all $(h,t)\in[H]\times[T]$, with probability at
least $1-\delta$, it holds that

$\sum_{z^{\prime}\in\mathcal{Z}}\sum_{i\in[t]}D_{\rm
H}^{2}\big{(}\mathbb{P}_{z}^{\pi^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z^{\prime}}^{\pi^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})\leq
2\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right),$

where denote $\breve{\tau}_{h/t}^{i}={\tau}_{H}$ for all $i<t$ and
$\breve{\tau}_{h/t}^{t}={\tau}_{h}$, and $\mathbb{P}_{z}^{\pi}(\tau_{h})$ is
defined in (A.3).

_Proof of Lemma C.1._ The proof is rather standard (e.g., see Geer, (2000)).
Let $\mathfrak{F}_{t}$ be the filtration induced by
$\\{\omega^{i},\tau_{H}^{i}\\}_{i<t}\cup\\{\operatorname{\mathds{1}}(\pi^{i}=\pi_{\texttt{exp}})\\}_{i\in[t]}$.
For all $(h,t,z^{\prime})\in[H]\times[T]\times\mathcal{Z}$, with probability
at least $1-\delta$, the information gain concerning $z^{\prime}$ satisfies
that

$\displaystyle
L_{h,t}(z^{\prime})=\sum_{i=1}^{t}\log\left(\frac{\mathbb{P}_{z^{\prime}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}(\breve{\tau}_{h/t}^{i})}\right)$
$\displaystyle\leq
2\log\mathbb{E}_{\mathfrak{F}_{1:t}}\left[\exp\left(\frac{1}{2}\sum_{i=1}^{t}\log\frac{\mathbb{P}_{z^{\prime}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}(\breve{\tau}_{h/t}^{i})}\right)\right]+2\log(|\mathcal{Z}|/\delta),$
(C.10)

where the inequality follows Lemma F.1 with $\lambda=1/2$ and a union bound
taken over $\mathcal{Z}$. Besides,

$\displaystyle\mathbb{E}_{\mathfrak{F}_{1:t}}\left[\exp\left(\frac{1}{2}\sum_{i=1}^{t}\log\frac{\mathbb{P}_{z^{\prime}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}(\breve{\tau}_{h/t}^{i})}\right)\right]=\prod_{i=1}^{t}\left(1-D_{\rm
H}^{2}\big{(}\mathbb{P}_{z}^{\pi^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z^{\prime}}^{\pi^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\right).$
(C.11)

Combine (C.10), (C.11) and fact that $\log(1-x)\leq-x$ for all $x\leq 1$, it
holds that

$L_{h,t}(z^{\prime})\leq-2\sum_{i=1}^{t}D_{\rm
H}^{2}\big{(}\mathbb{P}_{z}^{\pi^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z^{\prime}}^{\pi^{i}}(\breve{\tau}_{h/t}^{i})\big{)}+2\log(|\mathcal{Z}|/\delta),$
(C.12)

with probability greater than $1-\delta$. Based on the Donsker-Varadhan
representation in Lemma F.2 and duality principle, we have
$\log\mathbb{E}_{Q}[e^{f}]=\sup_{P\in\Delta(\mathcal{X})}\left\\{\mathbb{E}_{P}\left[f\right]-D_{\rm
KL}(P\hskip 1.42262pt\|\hskip 1.42262ptQ)\right\\}$, where the supremum is
taken at $P(x)\propto\exp(f(x))\cdot Q(x)$. Please refer to Lemma 4.10 in Van
Handel, (2014) for detailed proof. Based on the arguments above, for all
$(h,t,P)\in[H]\times[T]\times\Delta(\mathcal{Z})$, it holds

$\displaystyle\sum_{z^{\prime}\in\mathcal{Z}}L_{h,t}(z^{\prime})\cdot
P(z^{\prime})-D_{\rm KL}\big{(}P\hskip 1.42262pt\|\hskip
1.42262pt\mathcal{P}_{\mathcal{Z}}\big{)}\leq\sum_{z^{\prime}\in\mathcal{Z}}L_{h,t}(z^{\prime})\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})-D_{\rm
KL}\big{(}\mathbb{P}_{\mathcal{D}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\hskip 1.42262pt\|\hskip
1.42262pt\mathcal{P}_{\mathcal{Z}}\big{)}.$ (C.13)

since $\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\propto\exp\left(L_{h,t}(z^{\prime})\right)\cdot\mathcal{P}_{\mathcal{Z}}(z^{\prime})$
for all $(h,t)\in[H]\times[T]$. Let $\delta_{z}(\cdot)$ bs the Dirac
distribution over the singleton $z$. Following this, by taking $P=\delta_{z}$
in (C.13), we have

$\sum_{z^{\prime}\in\mathcal{Z}}L_{h,t}(z^{\prime})\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})\geq D_{\rm
KL}\big{(}\mathbb{P}_{\mathcal{D}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\hskip 1.42262pt\|\hskip
1.42262pt\mathcal{P}_{\mathcal{Z}}\big{)}+\log\mathcal{P}_{\mathcal{Z}}(z)\geq\log\mathcal{P}_{\mathcal{Z}}(z),$
(C.14)

where the first inequality uses $D_{\rm KL}(\delta_{z}(\cdot)\hskip
1.42262pt\|\hskip
1.42262pt\mathcal{P}_{\mathcal{Z}}(\cdot))=-\log\mathcal{P}_{\mathcal{Z}}(z)$
based on the definitions. Therefore, for all $(h,t)\in[H]\times[T]$, with
probability at least $1-\delta$, it holds that

$\displaystyle\sum_{z^{\prime}\in\mathcal{Z}}\sum_{i\in[t]}D_{\rm
H}^{2}\big{(}\mathbb{P}_{z}^{\pi^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z^{\prime}}^{\pi^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})$
$\displaystyle\leq-\sum_{z^{\prime}\in\mathcal{Z}}L_{h,t}(z^{\prime})/2\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})+\log\left(|\mathcal{Z}|/\delta\right)$
$\displaystyle\leq 2\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right),$
(C.15)

where the first inequality results from (C.11), and the last inequality
follows (C.14) and Assumption 4.5, which indicates that
$1/\mathcal{P}_{\mathcal{Z}}(z)\leq c_{\mathcal{Z}}|\mathcal{Z}|$. Thus, we
conclude the proof of Lemma C.1. $\Box$

###  C.4 Proof of Proposition 4.3

Our construction of the hard-to-distinguish example is a natural extension to
the hard instance for the contextual bandit problem in Proposition 1 (Zhang,,
2022).

###### Proof of Proposition 4.3..

Suppose that the high-level POMDP is fully observable, i.e.,
$\mathbb{O}(s)=s$, with $H=2$ and $|\Omega|$=1. Consider
$\mathcal{S}=\\{s_{1},s_{2},s_{3}\\}$ with rewards $r(s_{1})=0.5$,
$r(s_{2})=1$, $r(s_{3})=0$, $\mathcal{G}=\\{g_{1},g_{2}\\}$, and
$\mathcal{Z}=\\{z_{1},\dots,z_{N}\\}$. Starting from initial state $s_{1}$,
the transition kernel follows

$\left\\{\begin{aligned} &\mathbb{P}_{z_{i}}(s_{1}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{1})=1,\quad\mathbb{P}_{z_{i}}(s_{2}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{1})=0,\quad\mathbb{P}_{z_{i}}(s_{3}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{1})=0,\hskip 34.14322pt\forall i\in[N],\\\
&\mathbb{P}_{z_{1}}(s_{1}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{2})=0,\quad\mathbb{P}_{z_{1}}(s_{1}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{2})=1,\quad\mathbb{P}_{z_{1}}(s_{3}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{2})=0,\hskip 32.72049pt\text{if~{}}i=1,\\\
&\mathbb{P}_{z_{i}}(s_{1}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{2})=0,\quad\mathbb{P}_{z_{i}}(s_{2}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{2})=p_{i},\quad\mathbb{P}_{z_{i}}(s_{3}\hskip
1.42262pt|\hskip 1.42262pts_{1},g_{2})=1-p_{i},\quad\text{if~{}}i\neq
1,\end{aligned}\right.$

where $p_{i}=0.5(1-\frac{i}{N})$ for all $i\in[N]$. For latent environment
$z_{1}$, the optimal policy is $\pi^{*}_{z_{1},1}(s_{1})=g_{2}$ and
$\pi^{*}_{z_{i},1}(s_{1})=g_{1}$ if $i\neq 1$. Suppose that prior distribution
$\mathcal{P}_{\mathcal{Z}}$ is uniform. At $t=1$, without any information, the
posterior $\mathbb{P}(\cdot\hskip 1.42262pt|\hskip 1.42262pt\mathtt{pt}_{1})$
degenerates to prior $\mathcal{P}_{\mathcal{Z}}(\cdot)={\rm
Unif}_{\mathcal{Z}}(\cdot)$. Hence, the LLM’s policy at first step follows
that $\pi_{\mathtt{LLM}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts_{1})=\left(1-\frac{1}{N}\right)\cdot\delta_{g_{1}}(\cdot)+\frac{1}{N}\cdot\delta_{g_{2}}(\cdot).$
Since $\mathbb{P}_{z_{i}}(s_{1}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{1})=1$ and $\mathbb{P}_{z_{i}}(s_{2}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{1})=\mathbb{P}_{z_{i}}(s_{3}\hskip 1.42262pt|\hskip
1.42262pts_{1},g_{1})=0$ for all $i\in[N]$, taking subgoal $g_{1}$ provides no
information to differentiate $z_{i}$ from others, and the posterior remains
uniform. Such situation, i.e., $\mathbb{P}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{t})={\rm Unif}_{\mathcal{Z}}(\cdot)$, ends only if the
LLM suggests taking $g_{2}$ at some epsiode $t$. Consider the hard trajectory
$\tau_{\rm hard}=\\{s_{1},g_{1},s_{1}\\}_{t\in[T]}$, where LLM consistently
adheres to the initial $\pi_{\mathtt{LLM}}$ and keeps recommending subgoal
$g_{1}$. Thus, we have $\mathbb{P}_{z_{1}}(\tau_{\rm hard})=(1-1/N)^{T}$,
indicating ${\rm Reg}_{z_{1}}(T)\geq 0.5T\cdot(1-1/N)^{T}$. ∎

##  Appendix D Proof for Section 5: Practical Setting

###  D.1 Proof of Theorem 5.5

_Proof of Theorem 5.5._ Recall that the binary discriminator for label
$y\in\\{0,1\\}$ is defined as

$\mathbb{D}_{\gamma}(y\hskip 1.42262pt|\hskip
1.42262pto,s):=\left(\frac{f_{\gamma}(o,s)}{1+f_{\gamma}(o,s)}\right)^{y}\left(\frac{1}{1+f_{\gamma}(o,s)}\right)^{1-y},$

and the contrastive learning algorithm in (3.8) follows $\widehat{\gamma}={\rm
argmax}_{\gamma\in\Gamma}\
\mathbb{\widehat{E}}_{\mathcal{D}_{\mathtt{Rep}}}\big{[}\log\mathbb{D}_{\gamma}(y\hskip
1.42262pt|\hskip 1.42262pto,s)\big{]}$, and thus $f_{\widehat{\gamma}}$ is the
maximum likelihood estimator (MLE) concerning the dataset
$\mathcal{D}_{\mathtt{Rep}}$. Based on Lemma F.3, the MLE-type algorithm
ensures that, with probability at least $1-\delta$, it holds that

$\bar{\mathbb{E}}_{(o,s)\sim\mathcal{D}_{\mathtt{Rep}}}\left[D_{\rm
TV}^{2}\left(\mathbb{D}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s),\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)\right)\right]\leq{2\log(N_{\rm p}T_{\rm
p}H|\mathcal{F}_{\gamma}|/\delta)}/{N_{\rm p}T_{\rm p}H},$ (D.1)

where $\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)=\mathbb{D}_{\gamma^{*}}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)$ with $f_{\gamma^{*}}=f^{*}\in\mathcal{F}_{\gamma}$ denotes the
ground-truth discriminator based on the realizability in Assumption 5.4. Based
on the definition of total variation, it holds that

$\displaystyle D_{\rm TV}^{2}\left(\mathbb{D}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pto,s),\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)\right)$
$\displaystyle\quad=\left(\frac{f_{\widehat{\gamma}}(o,s)-f^{*}(o,s)}{(1+f_{\widehat{\gamma}}(o,s))(1+f^{*}(o,s))}\right)^{2}\leq\frac{1}{(1+R_{\mathcal{F}})^{2}}\left(\frac{f_{\widehat{\gamma}}(o,s)-f^{*}(o,s)}{1+f^{*}(o,s)}\right)^{2}$
$\displaystyle\quad=\frac{1}{(1+R_{\mathcal{F}})^{2}}\left(\frac{\mathbb{O}_{\widehat{\gamma}}(o\hskip
1.42262pt|\hskip 1.42262pts)-\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)}{\mathcal{P}^{-}(o)+\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)}\right)^{2}=\frac{1}{(1+R_{\mathcal{F}})^{2}}\left(\frac{\mathbb{\bar{O}}_{\widehat{\gamma}}(o\hskip
1.42262pt|\hskip 1.42262pts)-\mathbb{\bar{O}}(o\hskip 1.42262pt|\hskip
1.42262pts)}{\mathbb{\bar{O}}(o\hskip 1.42262pt|\hskip
1.42262pts)}\right)^{2},$ (D.2)

where the first inequality results from $\|f\|_{\infty}\leq R_{\mathcal{F}}$