Sequential planning in large state space and action space quickly becomes
intractable due to combinatorial explosion of the search space. Heuristic
methods, like monte-carlo tree search, though effective for large state space,
but struggle if action space is large. Pure reinforcement learning methods,
relying only on reward signals, needs prohibitively large interactions with the
environment to device a viable plan. If the state space, observations and
actions can be represented in natural language then Large Language models (LLM)
can be used to generate action plans. Recently several such goal-directed
agents like Reflexion, CLIN, SayCan were able to surpass the performance of
other state-of-the-art methods with minimum or no task specific training. But
they still struggle with exploration and get stuck in local optima. Their
planning capabilities are limited by the limited reasoning capability of the
foundational LLMs on text data. We propose a hybrid agent "neoplanner", that
synergizes both state space search with queries to foundational LLM to get the
best action plan. The reward signals are quantitatively used to drive the
search. A balance of exploration and exploitation is maintained by maximizing
upper confidence bounds of values of states. In places where random exploration
is needed, the LLM is queried to generate an action plan. Learnings from each
trial are stored as entity relationships in text format. Those are used in
future queries to the LLM for continual improvement. Experiments in the
Scienceworld environment reveals a 124% improvement from the current best
method in terms of average reward gained across multiple tasks.

通过结合状态空间搜索和基于自然语言模型的查询，我们提出了一种混合代理方法 neoplanner，以最大化状态值的上界来平衡探索和开发，并通过查询自然语言模型以生成行动计划，进一步提高了大规模状态空间和行动空间的顺序规划的性能。