Reinforcement Learning in Parametric MDPs with Exponential Families

Sayak Ray Chowdhury, Aditya Gopalan, Odalric-Ambrym MaillardAISTATS 2021 · OpenReview

Introduction

Reinforcement Learning (RL) in environments with massive or continuous state-action spaces requires agents to generalize from limited experiences. To achieve this, researchers typically impose structural assumptions on the underlying Markov Decision Process (MDP). However, existing parametric approaches often rely on restrictive assumptions—such as assuming the transition probability or the value function is a simple linear function of features. These models frequently fail to capture essential structures found in classical control, such as Linear Dynamical Systems (LDS), or complex interactions in Factored MDPs.

This paper introduces a flexible framework that models MDP transitions as linearly parameterized exponential families. By leveraging the natural geometry of exponential families, the authors propose algorithms that bridge the gap between classical control theory and modern structured RL, providing strong theoretical guarantees for regret minimization.

The Bilinear Exponential Family Model

The core contribution is the Bilinear Exponential Family transition model. Rather than assuming the transition probability $P$ is linear, the model assumes the logarithm of the density follows a bilinear form: $$P_\theta(s'|s, a) \propto \exp(\psi(s')^\top M_\theta \phi(s, a))$$ where $M_\theta$ is a matrix constructed from $d$ unknown parameters, and $\psi(s')$ and $\phi(s, a)$ are known feature mappings.

This formulation is significant because exponential families (including Gaussian, Bernoulli, and Poisson distributions) are the standard language of statistical modeling. This "log-linear" approach allows the model to represent a much wider array of natural phenomena than models assuming raw probabilities are linear. It effectively encompasses several classic benchmarks, including:

  • Linear Dynamical Systems (LDS): The foundation of control engineering.
  • Factored MDPs: Where state variables interact in structured ways.
  • Tabular MDPs: The standard discrete case.

Algorithms: Exp-UCRL and Exp-PSRL

The authors propose two primary algorithms to navigate the exploration-exploitation tradeoff in these MDPs:

  1. Exp-UCRL (Upper Confidence RL): This model-based algorithm uses penalized Maximum Likelihood Estimation (MLE) to learn the $d$-dimensional representation of the transition distribution. It maintains a "confidence set" of plausible MDPs and follows an optimistic strategy—selecting the policy that would be optimal for the best-case MDP within that set.
  2. Exp-PSRL (Posterior Sampling RL): A Bayesian alternative, similar to Thompson Sampling, which samples a transition model from a posterior distribution and executes the optimal policy for that specific sample.

A key technical innovation supporting these algorithms is a novel Laplace concentration inequality for conditional exponential families. This mathematical tool allows for the construction of tighter confidence regions based on Kullback-Leibler (KL) divergence rather than standard Euclidean distance. This shift to the "natural" geometry of the distribution is a primary driver of the algorithm's efficiency.

Theoretical Results

The paper provides a rigorous frequentist (worst-case) regret analysis for Exp-UCRL. The derived regret bound is: $$\tilde{O}(d\sqrt{H^3N})$$ where:

  • $d$ is the number of parameters.
  • $H$ is the planning horizon.
  • $N$ is the total number of time steps.

This bound is sub-linear in $N$, meaning the agent's performance converges toward the optimal policy over time. Notably, the bound is linear in the dimension $d$ and independent of the total number of states or actions, making it highly suitable for high-dimensional problems. Furthermore, the framework matches the best-known performance for Linear Dynamical Systems while offering much greater generality.

Discussion and Future Work

While the framework provides a powerful unification of control and RL, it faces practical challenges. The "Optimistic Planning" step in Exp-UCRL requires solving a complex optimization problem to find the best policy across a set of MDPs, which can be computationally expensive in continuous spaces. Additionally, the current proofs assume a "minimal representation" of the exponential family, and extending this to non-minimal families (with redundant parameters) remains an open technical challenge. Finally, the model currently assumes full observability; extending these results to Partially Observed MDPs (POMDPs) represents a significant frontier for future research.

Summary updated

Abstract

Extending model-based regret minimization strategies for Markov decision processes (MDPs) beyond discrete state-action spaces requires structural assumptions on the reward and transition models. Existing parametric approaches establish regret guarantees by making strong assumptions about either the state transition distribution or the value function as a function of state-action features, and often do not satisfactorily capture classical problems like linear dynamical systems or factored MDPs. This paper introduces a new MDP transition model defined by a collection of linearly parameterized exponential families with $d$ unknown parameters. For finite-horizon episodic RL with horizon $H$ in this MDP model, we propose a model-based upper confidence RL algorithm (Exp-UCRL) that solves a penalized maximum likelihood estimation problem to learn the $d$-dimensional representation of the transition distribution, balancing the exploitation-exploration tradeoff using confidence sets in the exponential family space. We demonstrate the efficiency of our algorithm by proving a frequentist (worst-case) regret bound that is of order $\tilde O(d\sqrt{H^3 N})$, sub-linear in total time $N$, linear in dimension $d$, and polynomial in the planning horizon $H$. This is achieved by deriving a novel concentration inequality for conditional exponential families that might be of independent interest. The exponential family MDP model also admits an efficient posterior sampling-style algorithm for which a similar guarantee on the Bayesian regret is shown.
BibTeX
@inproceedings{chowdhury2021reinforcement,
  author = {Sayak Ray Chowdhury and Aditya Gopalan and Odalric-Ambrym Maillard},
  title = {{Reinforcement Learning in Parametric MDPs with Exponential Families}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=0LMeUJiMB-C},
}
Figure