Introduction
Reinforcement Learning (RL) is notoriously sample-inefficient, often requiring millions of interactions to learn effective policies. However, in many real-world scenarios, taking one action can provide information about the outcomes of several others. This paper formalizes this "side observation" setting using feedback graphs, proving that the complexity of learning an environment depends on the graph's structure—specifically its "mas-number" ($M$)—rather than just the total number of states and actions ($SA$).
The Feedback Graph Framework
The authors introduce a framework where, at each step, the agent receives the standard transition $(s, a, r, s')$ plus additional "hypothetical" observations for other state-action pairs, as defined by a directed feedback graph $G$. This bridges the gap between graph-based feedback in Multi-Armed Bandits and the more complex world of episodic Markov Decision Processes (MDPs).
Algorithmic Approaches
The paper proposes two primary algorithms:
- Optimistic Model-Based RL (Algorithm 1): An extension of state-of-the-art algorithms like ORLC. The agent updates its internal model (transition and reward estimates) using all available side observations from the graph at every step.
- Dominating Set Exploration (Algorithm 2): Designed for cases where a small "dominating set" of state-action pairs exists. This two-stage algorithm first learns how to reach the dominating set and then visits those nodes to rapidly learn the rest of the environment.
Key Insights and Results
The central theoretical finding is that $M$ is the new $SA$. In standard tabular RL, regret typically scales with the number of states and actions. With feedback graphs, the dominant term in the regret bound depends on the mas-number $M$, which is the size of the largest acyclic subgraph. In dense graphs, $M$ can be significantly smaller than $S imes A$, leading to massive theoretical speedups.
As summarized in the table above, Algorithm 1 achieves a regret bound of $\tilde{O}(\sqrt{MH^2T} + MSH^2)$. For symmetric feedback graphs, this bound is proven to be minimax-optimal.
The Reachability Bottleneck
Unlike in bandits, where an informative arm can be pulled at any time, RL requires navigating to specific states. The authors prove that the benefit of a small "dominating set" is limited by $p_0$—the probability of being able to reach those informative states. This "reachability bottleneck" makes leveraging side observations in MDPs fundamentally harder than in bandit settings.
Limitations and Future Work
While this work provides a rigorous foundation for tabular MDPs, several challenges remain. The current model assumes an "oracle" provides side observations, which may be biased or noisy in practice. Furthermore, extending these graph-theoretic insights to function approximation (using neural networks for continuous state spaces) and model-free approaches like Q-learning are vital next steps for the field.
Summary updated