Recursive Reinforcement Learning

2022-06-23 · Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, Dominik Wojtczak

Recursion is the fundamental paradigm to finitely describe potentially infinite objects. As state-of-the-art reinforcement learning (RL) algorithms cannot directly reason about recursion, they must rely on the practitioner's ingenuity in designing a suitable "flat" representation of the environment. The resulting manual feature constructions and approximations are cumbersome and error-prone; their lack of transparency hampers scalability. To overcome these challenges, we develop RL algorithms capable of computing optimal policies in environments described as a collection of Markov decision processes (MDPs) that can recursively invoke one another. Each constituent MDP is characterized by several entry and exit points that correspond to input and output values of these invocations. These recursive MDPs (or RMDPs) are expressively equivalent to probabilistic pushdown systems (with call-stack playing the role of the pushdown stack), and can model probabilistic programs with recursive procedural calls. We introduce Recursive Q-learning -- a model-free RL algorithm for RMDPs -- and prove that it converges for finite, single-exit and deterministic multi-exit RMDPs under mild assumptions.

📄 PDF Abstract BibTeX arXiv:2206.11430

Code (0)

등록된 구현이 없습니다.

Tasks

IngenuityQ-Learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Recursive Agent Optimization

2026-05-07 · Apurva Gandhi, Satyaki Chakraborty, Xiangjun Wang, Aviral Kumar 외 arxiv

We introduce Recursive Agent Optimization (RAO), a reinforcement learning approach for training recursive agents: agents that can spawn and delegate sub-tasks to new instantiations of themselves recursively. Recursive ag…

Reinforcement Learning

Recursive Reasoning Graph for Multi-Agent Reinforcement Learning

2022-03-06 · Xiaobai Ma, David Isele, Jayesh K. Gupta, Kikuo Fujimura 외

Multi-agent reinforcement learning (MARL) provides an efficient way for simultaneously learning policies for multiple agents interacting with each other. However, in scenarios requiring complex interactions, existing alg…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

AgentOPSD: Recursive Self-Distillation for Agentic Reinforcement Learning

2026-08-06 · Zi-Han Wang, Zhengxi Lu, Zhiyuan Yao, Jinyang Wu 외 hf

Reinforcement learning (RL) with verifiable rewards constructs trajectory-level advantage estimates, yet it often fails to credit the few pivotal decisions that determine outcomes in long-horizon, multi-turn agentic task…

Reinforcement Learning

Learning Efficient Recursive Numeral Systems via Reinforcement Learning

2024-09-11 · Andrea Silvi, Jonathan Thomas, Emil Carlsson, Devdatt Dubhashi 외

It has previously been shown that by using reinforcement learning (RL), agents can derive simple approximate and exact-restricted numeral systems that are similar to human ones (Carlsson, 2021). However, it is a major ch…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient

2020-07-25 · Haonan Jia, Xiao Zhang, Jun Xu, Wei Zeng 외

Deep Q-learning algorithms often suffer from poor gradient estimations with an excessive variance, resulting in unstable training and poor sampling efficiency. Stochastic variance-reduced gradient methods such as SVRG ha…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)