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:
- 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.
- 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