Sequential decision-making algorithms such as reinforcement learning (RL) in
real-world scenarios inevitably face environments with partial observability.
This paper scrutinizes the effectiveness of a popular architecture, namely
Transformers, in Partially Observable Markov Decision Processes (POMDPs) and
reveals its theoretical limitations. We establish that regular languages, which
Transformers struggle to model, are reducible to POMDPs. This poses a
significant challenge for Transformers in learning POMDP-specific inductive
biases, due to their lack of inherent recurrence found in other models like
RNNs. This paper casts doubt on the prevalent belief in Transformers as
sequence models for RL and proposes to introduce a point-wise recurrent
structure. The Deep Linear Recurrent Unit (LRU) emerges as a well-suited
alternative for Partially Observable RL, with empirical results highlighting
the sub-optimal performance of the Transformer and considerable strength of
LRU.

这篇论文研究了在现实世界场景中，像强化学习（RL）这样的序贯决策算法不可避免地面对具有部分可观察性的环境，着重探讨了流行架构 Transformer 在部分可观察马尔可夫决策过程（POMDPs）中的有效性，并揭示了它的理论局限性，将可被 Transformer 难以建模的正则语言归约为 POMDPs，这对于 Transformer 在学习 POMDP 特定的归纳偏见构成了重大挑战，因为 Transformer 缺乏像 RNNs 这样的其他模型中固有的循环特性，该论文质疑了 Transformer 作为序列模型应用于 RL 的普遍信念，并提出引入逐点循环结构，深度线性循环单元（LRU）作为部分可观察 RL 的一个合适的替代品，并通过实证结果凸显了 Transformer 的次优性能和 LRU 的可观实力。

重新思考 Transformer 在解决 POMDP 中的应用

Rethinking Transformers in Solving POMDPs

While language models (LMs) offer significant capability in zero-shot
reasoning tasks across a wide range of domains, they do not perform
satisfactorily in problems which requires multi-step reasoning. Previous
approaches to mitigate this involves breaking a larger, multi-step task into
sub-tasks and asking the language model to generate proposals ("thoughts") for
each sub-task and using exhaustive planning approaches such as DFS to compose a
solution. In this work, we leverage this idea to introduce two new
contributions: first, we formalize a planning-based approach to perform
multi-step problem solving with LMs via Partially Observable Markov Decision
Processes (POMDPs), with the LM's own reflections about the value of a state
used as a search heuristic; second, leveraging the online POMDP solver POMCP,
we demonstrate a superior success rate of 89.4% on the Game of 24 task as
compared to existing approaches while also offering better anytime performance
characteristics than fixed tree-search which is used previously. Taken
together, these contributions allow modern LMs to decompose and solve
larger-scale reasoning tasks more effectively.

在本研究中，我们使用基于规划的方法结合部分可观察马尔可夫决策过程（POMDPs）来解决多步骤的问题，并通过 POMCP 在线求解器在 24 点游戏任务上展现出了 89.4% 的优越成功率，同时也提供了比之前使用的固定树搜索更好的任意时间性能。

思路规划：以启发式引导的大型语言模型问题解决方案

Plan of Thoughts: Heuristic-Guided Problem Solving with Large Language  Models

This paper extends the framework of partially observable Markov decision
processes (POMDPs) to multi-agent settings by incorporating the notion of agent
models into the state space. Agents maintain beliefs over physical states of
the environment and over models of other agents, and they use Bayesian updates
to maintain their beliefs over time. The solutions map belief states to
actions. Models of other agents may include their belief states and are related
to agent types considered in games of incomplete information. We express the
agents autonomy by postulating that their models are not directly manipulable
or observable by other agents. We show that important properties of POMDPs,
such as convergence of value iteration, the rate of convergence, and piece-wise
linearity and convexity of the value functions carry over to our framework. Our
approach complements a more traditional approach to interactive settings which
uses Nash equilibria as a solution paradigm. We seek to avoid some of the
drawbacks of equilibria which may be non-unique and do not capture
off-equilibrium behaviors. We do so at the cost of having to represent, process
and continuously revise models of other agents. Since the agents beliefs may be
arbitrarily nested, the optimal solutions to decision making problems are only
asymptotically computable. However, approximate belief updates and
approximately optimal plans are computable. We illustrate our framework using a
simple application domain, and we show examples of belief updates and value
functions.

本研究在部分可观察马尔可夫决策过程 (POMDPs) 的基础上，将代理模型纳入到状态空间中，使其扩展到了多智能体的情景下。代理人通过贝叶斯更新来维护对物理环境状态和其他代理模型的信念，并使用基于置信状态的映射来求得最优方案。虽然我们的方法中代理人的模型不可直接被操纵或观察，但我们证明了 POMDPs 的重要特性如收敛率、价值函数的分段线性和凸性等在我们的框架下仍然成立。