Log-normality and Skewness of Estimated State/Action Values in Reinforcement Learning

Liangpeng Zhang, Ke Tang, Xin Yao

Introduction

In Reinforcement Learning (RL), agents make decisions by comparing estimated state values ($\hat{V}$) or action values ($\hat{Q}$). While much of the existing research has focused on bias—such as the systematic overestimation famously seen in Q-learning due to the max operator—this paper investigates a more subtle issue: the shape of the distribution of these estimates.

The authors reveal that RL value estimators are fundamentally prone to skewed distributions, specifically log-normal distributions. They identify a hidden trap: even if an estimator is mathematically "unbiased" (meaning its average over infinite trials is perfectly correct), its distribution might be heavily lopsided. If the distribution has a long "tail" of high values, the most frequent estimates (the median) will be significantly lower than the true mean. Consequently, an agent will likely underestimate state values in the majority of individual trials, leading it to discard potentially high-value policies simply because their value estimates are "unlucky" more often than not.

Skewed distributions of estimated values

Methodology

The authors provide a theoretical framework to decompose the Bellman equation into a statistical model to analyze this skewness:

  1. Decomposition into NSR-MCs: Complex Markov Decision Processes (MDPs) are broken down into simpler "Normalised Single-reward Markov Chains."
  2. Path-wise Analysis: These chains are further decomposed into individual "representative paths."
  3. Statistical Proof of Log-normality: Because state values are essentially products of estimated transition probabilities along these paths, the Central Limit Theorem applies in the logarithmic domain. Consequently, the estimated values ($\hat{V}$) mathematically follow a log-normal distribution.
  4. Skewness Measurement: The researchers use the Pearson 2 coefficient—which measures the distance between the mean and the median—to quantify how "lopsided" the value estimates are.

To validate these theoretical findings, the paper uses two primary environments: a synthetic Chain MDP (a linear environment where an agent moves through $n$ states to reach a goal, isolating variables like transition probability and reward values) and a Complex Maze (a 440-state grid-world featuring traps and complicated transition patterns to test realistic discrete environments).

Key Insights

  • The "Product" Problem: The core reason for skewness is that the Bellman equation involves multiplying probabilities. In statistics, the product of many independent random variables tends toward a log-normal distribution, which is naturally skewed.
  • Unbiased $\neq$ Reliable: An agent might have an unbiased estimator but still fail because the probability of underestimating a state's value is much higher than 50% (often 60-70% in their tests).
  • Reward Sign Dictates Skew: The sign of the reward fundamentally changes the nature of the skew. Positive rewards lead to positive skew (frequent underestimation), while Negative rewards lead to negative skew (frequent overestimation).
  • Diminishing Returns of Data: While collecting more samples reduces skewness, it does so at a decreasing rate. Doubling your data doesn't necessarily halve your skewness problem.

Empirical Results

The empirical experiments strongly matched the theoretical predictions. In the Chain MDP experiment, even with 200 observations per state-action pair, the state value was underestimated in 60.3% of the runs. This underestimation proved to be the norm rather than the exception.

Empirical vs. theoretical distribution and the probability of underestimation

In the complex maze, the optimal state value was underestimated 67.6% of the time when sample sizes were small ($m=10$). The authors demonstrated that the probability of underestimation follows an exponential-like decay as more observations are collected. However, in the complex maze, even with 200 observations, the probability of underestimation remained stubbornly high at above 55%.

Crucially, the empirical distributions from their experiments matched their theoretical log-normal predictions with high statistical significance, failing to reject the log-normal hypothesis in a Kolmogorov-Smirnov test ($p$-value of 0.1190).

Limitations and Future Work

The analysis is primarily rooted in tabular RL and model-based methods. While the authors argue the logic applies to model-free methods (like DQN), the interaction with deep neural networks and function approximation is not explicitly tested in this work.

Furthermore, while the authors suggest that "balancing" positive and negative rewards could neutralize skewness via reward shaping, they do not provide a specific, automated algorithm for doing this dynamically during training. Future directions include investigating how this log-normal skewness interacts with modern techniques like Monte-Carlo Tree Search (MCTS) or Policy Gradient methods, which might possess their own inherent skewness dynamics.

Summary updated

Abstract

Under/overestimation of state/action values are harmful for reinforcement learning agents. In this paper, we show that a state/action value estimated using the Bellman equation can be decomposed to a weighted sum of path-wise values that follow log-normal distributions. Since log-normal distributions are skewed, the distribution of estimated state/action values can also be skewed, leading to an imbalanced likelihood of under/overestimation. The degree of such imbalance can vary greatly among actions and policies within a single problem instance, making the agent prone to select actions/policies that have inferior expected return and higher likelihood of overestimation. We present a comprehensive analysis to such skewness, examine its factors and impacts through both theoretical and empirical results, and discuss the possible ways to reduce its undesirable effects.
BibTeX
@inproceedings{zhang2017log,
  author = {Liangpeng Zhang and Ke Tang and Xin Yao},
  title = {{Log-normality and Skewness of Estimated State/Action Values in Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
}
Figure