Reinforcement Learning with Feedback Graphs

Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, Karthik Sridharan

A major bottleneck in real-world Reinforcement Learning (RL) is sample complexity. Agents typically require millions of trials to learn a capable policy because they only gain information from the specific actions they execute. However, in many practical domains—such as robotics or medical treatment—we possess prior domain knowledge or auxiliary sensors. For example, a robot's line-of-sight sensors might reveal what would have happened had it moved left instead of forward, or a doctor might know that two related drugs will yield similar patient outcomes.

This paper explores how to make RL significantly more efficient by leveraging these "side observations." By formalizing domain knowledge as a feedback graph, the authors demonstrate that an agent can learn an optimal policy with far fewer interactions than traditional tabular RL theory suggests.

The Feedback Graph Framework

The core challenge is mathematically formalizing this "side information" to prove it accelerates learning. While previous work addressed this in the simpler Multi-Armed Bandit setting, RL introduces the complexity of navigating a Markov Decision Process (MDP) to reach informative states.

The authors formalize this using Feedback Graphs. In this framework, nodes represent state-action pairs $(s, a)$. A directed edge from $(s, a)$ to $(\bar{s}, \bar{a})$ indicates that when the agent executes $(s, a)$, an "oracle" simultaneously provides a hypothetical sample transition for $(\bar{s}, \bar{a})$.

Learning Protocol and Maze Example

To exploit this structure, the paper proposes two primary algorithms:

  1. Optimistic Model-Based RL: A standard model-based approach modified to update its internal world model using all samples provided by the oracle, rather than just the single transition the agent actually experienced.
  2. Dominating Set RL: A novel two-phase algorithm designed for environments where a small "dominating set" of state-action pairs can reveal information about the entire MDP. In Phase 1, the agent learns policies to reach these highly informative pairs. In Phase 2, it repeatedly visits them to rapidly build an accurate model of the whole environment.

Key Insights: Graph Properties Dictate Complexity

In standard tabular RL, regret scales with the square root of the number of states times actions ($\sqrt{SA}$). A breakthrough insight of this paper is that with feedback graphs, sample complexity scales with specific graph-theoretic properties instead of the raw state-action space.

Examples of Graph Properties
  • The Mas-number ($\mu$) Replaces $SA$: The authors prove that regret scales with $\sqrt{\mu}$, where $\mu$ is the size of the maximum acyclic subgraph (the "mas-number"). In many structured problems, $\mu$ is significantly smaller than $SA$ ($\mu \ll SA$), leading to massive theoretical speedups.
  • The Domination Number ($\gamma$): For environments with a small dominating set ($\gamma$), the leading term of sample complexity scales with $\gamma/\epsilon^2$ rather than $SA/\epsilon^2$.
  • The "Reaching" Problem: Unlike bandits where an agent can simply "pull an arm" to get information, an RL agent must learn how to navigate to informative states. This creates a dependency on $p_0$, the probability of reaching the hardest-to-access node in the dominating set.
  • Fundamental Limits: The authors provide lower bounds proving that learning cannot completely escape the "independence number" ($\alpha$) of the graph. This confirms that RL with side observations is fundamentally harder than the bandit equivalent due to the sequential nature of MDPs.

Multi-Task RL as a Graph

Beyond single-agent navigation, the authors elegantly show that learning multiple tasks with identical dynamics but different reward functions can be modeled as a specific type of feedback graph. This formulation allows an agent to "solve" $m$ simultaneous tasks with nearly the same sample complexity as solving a single task, showcasing the versatility of the feedback graph framework.

Key Results and Limitations

The theoretical results are robust: the authors achieve a regret bound of $\tilde{O}(\sqrt{\mu H^2 T})$, successfully replacing the total state-action space with the graph's mas-number. Furthermore, for undirected feedback graphs (where information flow is symmetric), they demonstrate that their regret bound is minimax-optimal.

However, the framework has current limitations that pave the way for future work:

  • Tabular Assumption: The results are confined to tabular MDPs. Extending these graph-theoretic bounds to deep RL with continuous spaces and function approximation remains a major open challenge.
  • Known Graph Structure: The primary algorithms assume the agent knows the structure of the feedback graph a priori. While the authors touch upon unknown graphs, developing a robust theory for simultaneously learning the graph structure and the optimal policy is necessary for broader real-world application.
  • Computational Overhead: While highly sample-efficient, the planning steps required to compute policies over these graphs can become computationally expensive as the state space grows.

Summary updated

Abstract

We study RL in the tabular MDP setting where the agent receives additional observations per step in the form of transitions samples. Such additional observations can be provided in many tasks by auxiliary sensors or by leveraging prior knowledge about the environment (e.g., when certain actions yield similar outcome). We formalize this setting using a feedback graph over state-action pairs and show that model-based algorithms can incorporate additional observations for more sample-efficient learning. We give a regret bound that predominantly depends on the size of the maximum acyclic subgraph of the feedback graph, in contrast with a polynomial dependency on the number of states and actions in the absence of side observations. Finally, we highlight fundamental challenges for leveraging a small dominating set of the feedback graph, as compared to the well-studied bandit setting, and propose a new algorithm that can use such a dominating set to learn a near-optimal policy faster.
BibTeX
@inproceedings{dann2020reinforcement,
  author = {Christoph Dann and Yishay Mansour and Mehryar Mohri and Ayush Sekhari and Karthik Sridharan},
  title = {{Reinforcement Learning with Feedback Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=B4lZQE-bz7c},
}
Figure