RAAM: The Benefits of Robustness in Approximating Aggregated MDPs in Reinforcement Learning

Marek Petrik, Dharmashankar SubramanianNeurIPS 2014 · OpenReview

TL;DR

RAAM (Robust Approximation for Aggregated MDPs) is a novel approach that significantly improves the reliability of state aggregation in Reinforcement Learning (RL). By reframing state aggregation as a Robust Markov Decision Process (RMDP), the authors reduce the theoretical performance loss bound by a factor of $1/(1-\gamma)$. This makes the algorithm much more stable for long-horizon problems without adding significant computational cost.

What Problem Does This Paper Address?

In Reinforcement Learning, "state aggregation" is a popular technique for handling massive state spaces. It works by grouping similar states together into "buckets" to simplify the problem. While simple and interpretable, it has a major flaw: as the discount factor $\gamma$ (which determines how much the agent cares about future rewards) approaches 1, the potential for error explodes.

Standard aggregation methods have a performance loss bound that grows quadratically with the horizon, specifically $O(1/(1-\gamma)^2)$. This happens because the algorithm might accidentally choose a sub-optimal policy that looks good on average within an aggregate bucket but performs terribly in specific underlying states. In practice, this means that even if you have a "good" approximation of the optimal value function, your agent might still behave poorly if the discount factor is high.

Methods

The authors introduce RAAM, which treats the uncertainty inherent in state aggregation with Robust Optimization.

  1. Robust MDP Formulation: Instead of assuming a fixed distribution of states within an aggregate "bucket," RAAM assumes an adversary (nature) will choose the worst-case distribution of states. This makes the agent's policy "robust" to approximation errors.
  2. $L_1$ Uncertainty Sets: The authors use $L_1$ norm constraints to define how much the state importance weights can deviate from a baseline. This allows for a continuous trade-off between standard aggregation and full robustness.
  3. Efficient Bellman Updates: Solving Robust MDPs is usually computationally expensive (often requiring Linear Programming). The authors developed a specialized linear-time algorithm for the Bellman update. By using a quantile selection approach, they make the robust update nearly as fast as a standard non-robust update.

Experimental Setup

The authors evaluated RAAM using a modified Inverted Pendulum problem, a classic benchmark in control and RL.

  • Setup: They used a $40 \times 40$ grid for state aggregation and uniform sampling for transitions.
  • The "Trap": To test robustness, they added an "extra reward" that could only be achieved by a sub-optimal policy. This reward was designed to "lure" standard aggregation methods into choosing a poor policy due to approximation errors.

Key Insights and Ideas

  • Robustness as a Regularizer: The core insight is that robustness isn't just for dealing with noisy sensors or changing environments; it's a powerful tool for mitigating approximation error introduced by the modeler.
  • Breaking the Quadratic Bound: By using a robust model, the authors prove the performance loss bound improves to $O(1/(1-\gamma))$. For a discount factor of 0.99, this is a 100x improvement in the theoretical error guarantee.
  • Computational "Free Lunch": Through clever algorithm design, the authors show that you can gain this robustness with minimal additional computational cost, debunking the idea that robust RL is too slow for practical use.

Key Results

  • Theoretical Stability: The paper provides a new, tighter bound on performance loss: $\rho(\pi^*) - \rho(\tilde{\pi}) \leq 2\epsilon(v^*)/(1-\gamma)$.
  • Empirical Performance: In the Inverted Pendulum experiments, standard aggregation and Approximate Linear Programming (ALP) failed as the "tempting" sub-optimal reward increased. RAAM remained stable and maintained a high return.
Mean return comparison showing RAAM's stability against sub-optimal rewards.
  • Speed: The custom C++ implementation of RAAM's update rule was orders of magnitude faster than a general-purpose LP solver (CPLEX) and performed similarly to standard, non-robust aggregation methods.
Computation time comparison showing the efficiency of the custom C++ implementation.

Limitations and Future Work

  • Parameter Tuning: The robustness parameter $\omega$ and the initial state weights $w$ are currently treated as hyperparameters. While the authors provide some theoretical justification for their choice, in practice, these may require manual tuning or "regularization" style treatment.
  • Meta-Actions: The current version of RAAM focuses on basic state aggregation. The authors suggest that extending this to "meta-actions" or "options" (hierarchical RL) could be a promising next step.
  • Alternative Norms: While the $L_1$ norm was used for efficiency, future work could explore other uncertainty sets, such as those based on KL divergence or different polynomial norms, which might offer different performance characteristics.

Summary updated

Abstract

We describe how to use robust Markov decision processes for value function approximation with state aggregation. The robustness serves to reduce the sensitivity to the approximation error of sub-optimal policies in comparison to classical methods such as fitted value iteration. This results in reducing the bounds on the gamma-discounted infinite horizon performance loss by a factor of 1/(1-gamma) while preserving polynomial-time computational complexity. Our experimental results show that using the robust representation can significantly improve the solution quality with minimal additional computational cost.
BibTeX
@inproceedings{petrik2014raam,
  author = {Marek Petrik and Dharmashankar Subramanian},
  title = {{RAAM: The Benefits of Robustness in Approximating Aggregated MDPs in Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=HJ-WBdbuZH},
}
Figure