A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning

2024-06-21 · Gianluca Drappo, Alberto Maria Metelli, Marcello Restelli

Hierarchical Reinforcement Learning (HRL) approaches have shown successful results in solving a large variety of complex, structured, long-horizon problems. Nevertheless, a full theoretical understanding of this empirical evidence is currently missing. In the context of the \emph{option} framework, prior research has devised efficient algorithms for scenarios where options are fixed, and the high-level policy selecting among options only has to be learned. However, the fully realistic scenario in which both the high-level and the low-level policies are learned is surprisingly disregarded from a theoretical perspective. This work makes a step towards the understanding of this latter scenario. Focusing on the finite-horizon problem, we present a meta-algorithm alternating between regret minimization algorithms instanced at different (high and low) temporal abstractions. At the higher level, we treat the problem as a Semi-Markov Decision Process (SMDP), with fixed low-level policies, while at a lower level, inner option policies are learned with a fixed high-level policy. The bounds derived are compared with the lower bound for non-hierarchical finite-horizon problems, allowing to characterize when a hierarchical approach is provably preferable, even without pre-trained options.

📄 PDF Abstract BibTeX arXiv:2406.15124

Code (0)

등록된 구현이 없습니다.

Tasks

Hierarchical Reinforcement Learning

Discovering Options for Exploration by Minimizing Cover Time

2019-03-02 · Yuu Jinnai, Jee Won Park, David Abel, George Konidaris

One of the main challenges in reinforcement learning is solving tasks with sparse reward. We show that the difficulty of discovering a distant rewarding state in an MDP is bounded by the expected cover time of a random w…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Exploration--Exploitation in MDPs with Options

2017-03-25 · Ronan Fruit, Alessandro Lazaric

While a large body of empirical results show that temporally-extended actions and options may significantly affect the learning performance of an agent, the theoretical understanding of how and when options can be benefi…

Reinforcement Learning Reinforcement Learning (RL)

Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations

2022-06-17 · Vignesh Viswanathan, Yair Zick

We study fair allocation of indivisible goods when agents have matroid rank valuations. Our main contribution is a simple algorithm based on the colloquial Yankee Swap procedure that computes provably fair and efficient …

Provably Faster Algorithms for Bilevel Optimization

2021-06-08 · NeurIPS 2021 12 · Junjie Yang, Kaiyi Ji, Yingbin Liang

Bilevel optimization has been widely applied in many important machine learning applications such as hyperparameter optimization and meta-learning. Recently, several momentum-based algorithms have been proposed to solve …

Bilevel Optimization Hyperparameter Optimization Meta-Learning

Exploration in Reinforcement Learning with Deep Covering Options

2020-05-01 · ICLR 2020 1 · Yuu Jinnai, Jee Won Park, Marlos C. Machado, George Konidaris

While many option discovery methods have been proposed to accelerate exploration in reinforcement learning, they are often heuristic. Recently, covering options was proposed to discover a set of options that provably red…