Online Reinforcement Learning for Mixed Policy Scopes

Junzhe Zhang, Elias BareinboimNeurIPS 2022 · OpenReview

Overview

In standard reinforcement learning (RL), agents typically operate under a fixed "policy scope"—meaning they consistently observe the same state variables and choose from an identical set of actions. However, real-world scenarios often demand more flexibility. In medicine, for example, treating a condition like alcohol use disorder might involve prescribing medication based on clinical history, or recommending behavioral therapy based on social context. These represent distinct strategies with different "scopes."

This paper introduces a novel framework for online RL where an agent must navigate and optimize across these mixed policy scopes. By leveraging causal diagrams and a unique "c-component" parametrization, the authors develop algorithms that achieve sublinear regret, effectively learning optimal treatment strategies even when available information and intervention options vary.

The Challenge of Mixed Scopes

Traditional RL struggles with mixed scopes because it lacks a built-in mechanism to share information across different observational and action spaces. If an agent tests a medication policy, standard RL doesn't naturally apply those learnings to a behavioral therapy policy. The core challenge is to find the optimal policy across a combinatorial space of mixed scopes while minimizing "regret"—the cumulative loss from not choosing the best possible action from the start.

Causal diagrams illustrating different policy scopes

Causal Reinforcement Learning Methods

To bridge RL and Causal Inference, the authors propose a framework built on several key pillars:

1. Causal Invariance: The environment is represented using a causal diagram (a Directed Acyclic Graph). This allows the agent to "reuse" data. Observations from a policy using one scope can help estimate the effects of a policy using another, provided they share underlying causal mechanisms.

2. Canonical Representation and MINCOLLECT: To make the optimization mathematically tractable, the complex global system is decomposed into smaller, independent "c-components" (confounded components). The authors introduce the MINCOLLECT algorithm to find a minimal set of these components. This significantly reduces the number of parameters the agent needs to learn, stripping away redundant information.

The MINCOLLECT algorithm for finding minimal c-components

3. Causal-UCB*: Following the "optimism in the face of uncertainty" principle, this algorithm maintains a confidence set of possible Structural Causal Models (SCMs) and selects the policy that performs best under the most optimistic model.

4. Causal-TS*: Because the UCB approach can be computationally expensive (NP-hard), the authors also propose a Thompson Sampling variant. CAUSAL-TS* uses Dirichlet priors over causal parameters and samples a model to decide the next action, offering a much more efficient solution for practical implementation.

Key Insights and Results

The algorithms were evaluated using randomly generated synthetic SCMs, including models inspired by alcohol use disorder and cardiovascular disease treatments.

  • Sample Efficiency through Geometry: The causal structure acts as a bridge between different policy scopes. If two policies affect the same part of the causal graph, the agent learns about that mechanism simultaneously for both.
  • Sublinear Regret: The authors mathematically prove that CAUSAL-UCB* achieves sublinear cumulative regret, meaning the agent's average performance converges to the optimal strategy over time.
  • Superiority over Baselines: In simulations, the causal Thompson Sampling approach (CAUSAL-TS*) consistently outperformed standard Randomized Controlled Trials (which explore blindly), standard TS (which treats every policy as an isolated bandit arm), and simplified TS variants that don't fully utilize c-component decomposition.
  • Redundancy Pruning: The framework mathematically detects if a scope is "redundant" (e.g., adding a variable that doesn't improve the reward). Pruning these accelerates learning and reduces the cardinality of the latent spaces.

Limitations and Future Directions

While a significant step forward, the framework currently assumes observed variables are discrete and finite, making continuous variables (like exact dosages) a challenge for future work. Additionally, planning in complex causal models remains computationally demanding as variables scale. Finally, the algorithms assume the causal diagram is known a priori. In many real-world applications, the graph itself is uncertain, pointing toward a need to integrate "causal discovery" directly into the RL loop.

Summary updated

Abstract

Combination therapy refers to the use of multiple treatments -- such as surgery, medication, and behavioral therapy - to cure a single disease, and has become a cornerstone for treating various conditions including cancer, HIV, and depression. All possible combinations of treatments lead to a collection of treatment regimens (i.e., policies) with mixed scopes, or what physicians could observe and which actions they should take depending on the context. In this paper, we investigate the online reinforcement learning setting for optimizing the policy space with mixed scopes. In particular, we develop novel online algorithms that achieve sublinear regret compared to an optimal agent deployed in the environment. The regret bound has a dependency on the maximal cardinality of the induced state-action space associated with mixed scopes. We further introduce a canonical representation for an arbitrary subset of interventional distributions given a causal diagram, which leads to a non-trivial, minimal representation of the model parameters.
BibTeX
@inproceedings{zhang2022online,
  author = {Junzhe Zhang and Elias Bareinboim},
  title = {{Online Reinforcement Learning for Mixed Policy Scopes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=sjaQ2bHpELV},
}
Figure