Hierarchical Reinforcement Learning promises, among other benefits, to efficiently capture and utilize the temporal structure of a decision-making problem and to enhance transfer learning capabilities, but theoretical guarantees lag behind practice. In this paper, we propose a Feudal Q-learning scheme and investigate under which conditions its coupled updates converge and are stable. By leveraging the theory of Stochastic Approximation and the ODE method, we present a theorem stating the convergence and stability properties of Feudal Q-learning. This provides a principled convergence and stability analysis tailored to Feudal RL. Moreover, we show that the updates converge to a point that can be interpreted as an equilibrium of a suitably defined game, opening the door to game-theoretic approaches to Hierarchical RL. Lastly, experiments based on the Feudal Q-learning algorithm support the outcomes anticipated by theory.
Figures & tables
Figure 1: Block diagram of the Feudal RL scheme. Instead of having a flat policy interacting with the system, there is a high-level policy, πh , selecting goals for a low-level policy, πl , that interacts with the system P .
Figure 2: Time scales of the high-level and low-level MDPs. Circles represent the states of the real system, while black circles indicate the states where the high-level MDP makes a decision. In this example, the high-level MDP makes a decision every T=3 time steps of the low-level MDP.
Symbol
Meaning
ak
Low-level action at time step k .
A
Action space of the original MDP.
γ , γh , γl
Discount factors.
M , Mh , Ml
Original, high-, and low-level MDP.
ωth
High-level action at time step t .
ωkl
Goal, at time step k , that the low-level policy should achieve.
Table 1: Table summarizing the main symbols.
Figure 3: First room of the Four Rooms Minigrid environment. The red triangle represents the initial pose of the agent, while the green square is the tile to reach. Grey tiles represent walls, while black tiles are walkable areas. Lit tiles help recognize the direction the agent is facing.
Figure 4: Cumulative reward per episode in the two trainings. The experiment clearly shows the convergent behaviour predicted by Theorem 1 . Moreover, the HRL agent is converging to the same cumulative reward as the standard Q-learning agent.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
We consider a federated reinforcement learning setting involving M agents, all of whom interact with a common Markov Decision Process (MDP). The agents exchange information via a central server to learn the optimal value function. Our goal is to understand to what extent one can hope for collaborative sample-complexity speedups in such a setting, when a small fraction of the agents are adversarial and can act arbitrarily. To that end, we propose Robust Fed-Q}, a federated Q-learning algorithm that blends ideas from both model-based and model-free RL, along with the median-of-means device from robust statistics. We prove that despite corruption, with high-probability, Robust Fed-Q (i) guarantees exact convergence to the optimal value function in the limit of infinite samples, and (ii) enjoys near-optimal finite-time rates that benefit from collaboration. In addition, our approach requires just O~(1) rounds of communication to achieve each of the above guarantees, a feature of independent interest in FL where communication is the major bottleneck.
Sreejeet Maity, Aritra Mitra
Department of Electrical and Computer Engineering, North Carolina State University
We present HBPI-UCRL, a model-based algorithm for hierarchical reinforcement learning (HRL) that learns high-level and low-level policies in parallel. HBPI-UCRL exploits the fact that a high-level transition corresponds to a multi-step transition at the low level. We introduce two conditions on the low-level dynamics that are sufficient to make parallel HRL learnable. When these conditions hold, we prove that HBPI-UCRL has a polynomial sample complexity in the problem parameters. In the sparse-reward, goal-directed setting, our sample complexity upper bound for HBPI-UCRL is strictly lower than that of its non-hierarchical counterpart, providing theoretical justification for the empirical success of HRL.
Anders Jonsson, Emilie Kaufmann, Gianmarco Tedeschi +1
Department of Engineering Universitat Pompeu Fabra · Univ. Lille, CNRS, Inria Centrale Lille, UMR 9189-CRIStAL · Dept. Electronics, Information, and Bioengineering Politecnico di Milano
Reinforcement learning has been successful both empirically and theoretically in single-agent settings, but extending these results to multi-agent reinforcement learning in general-sum Markov games remains challenging. This paper studies the convergence of Stackelberg Q-value iteration in two-player general-sum Markov games from a control-theoretic perspective. We introduce a relaxed policy condition tailored to the Stackelberg setting and model the learning dynamics as a switching system. By constructing upper and lower comparison systems, we establish finite-time error bounds for the Q-functions and characterize their convergence properties. Our results provide a novel control-theoretic perspective on Stackelberg learning. Moreover, to the best of the authors' knowledge, this paper offers the first finite-time convergence guarantees for Q-value iteration in general-sum Markov games under Stackelberg interactions.
Narim Jeong, Donghwan Lee
Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, 34141, South Korea