Value Function in Frequency Domain and the Characteristic Value Iteration Algorithm

Amir-massoud FarahmandNeurIPS 2019

Introduction

Standard Reinforcement Learning (RL) typically focuses on maximizing the expected return of a policy. However, this approach ignores the variance and inherent risk associated with different actions. Distributional RL (DistRL) bridges this gap by estimating the entire probability distribution of returns. While existing DistRL methods represent these distributions in the "spatial" domain—using probability density functions, categorical bins, or quantiles—this paper introduces a radical paradigm shift: representing the uncertainty of returns in the frequency domain.

By leveraging the Characteristic Function (CF)—the Fourier transform of a probability distribution—the authors unlock new mathematical tools for manipulating and estimating return uncertainty, establishing a rigorous theoretical foundation for frequency-domain RL.

The Characteristic Value Function (CVF)

The cornerstone of this framework is the Characteristic Value Function (CVF). Instead of relying on a standard value function $V^\pi(x)$ or a spatial return distribution $Z^\pi(x)$, the authors define the CVF, denoted as $\tilde{V}^\pi(\omega; x)$. This represents the characteristic function of the return random variable at a given state $x$ and frequency $\omega$.

Transforming the return distribution into the frequency domain fundamentally alters the structure of the Bellman equation. Unlike the standard additive Bellman equation ($R + \gamma V$), the frequency-domain Bellman equation becomes multiplicative: $$ \tilde{V}^\pi(\omega; x) = \tilde{R}(\omega; x) \int \mathcal{P}^\pi(dy|x) \tilde{V}^\pi(\gamma\omega; y) $$

Characteristic Value Iteration (CVI)

Despite this radical shift in representation, the core machinery of dynamic programming remains intact. The authors prove that the new multiplicative Bellman operator is a contraction mapping under specific frequency-weighted distance metrics ($d_{1,p}$ and $d_{\infty,p}$).

Because the operator is a contraction, iterative methods are guaranteed to converge to the true distribution of returns. This leads to the introduction of two algorithms:

  1. Characteristic Value Iteration (CVI): An iterative dynamic programming algorithm, analogous to standard Value Iteration, designed to find the fixed-point CVF.
  2. Approximate CVI (ACVI): To handle large state spaces and unknown environment dynamics, ACVI uses regression to estimate the conditional mean of the CVF from sampled transitions. It minimizes an empirical risk over the frequency domain to approximate the true distribution.

Theoretical Guarantees

While the paper is purely theoretical and does not include empirical benchmark evaluations, it provides robust mathematical guarantees for the ACVI algorithm:

  • Error Propagation: The authors' analysis reveals that ACVI behaves similarly to standard Approximate Value Iteration. Errors made in early iterations decay exponentially fast (by a factor of $\gamma$). After $K$ iterations, the distance to the optimal CVF is bounded by the geometrically discounted sum of approximation errors at each step: $\sum_{i=0}^K \gamma^i \|\tilde{\varepsilon}_{K+1-i}\|_{\infty,1} + \gamma^K d_{\infty,1}(\tilde{R}, \tilde{V}^\pi)$.
  • Bridging Frequency and Spatial Domains: A major theoretical hurdle is proving that a good approximation in the frequency domain translates to a meaningful result in the real world. The authors successfully prove that a small error in the CVF mathematically guarantees a small error in the actual probability distribution. Specifically, the 2-smooth Wasserstein distance between the estimated and true return distributions is bounded by $O(\max \|\tilde{\varepsilon}_i\|_{\infty, 1} + \gamma^K R_{\max})$.

Limitations and Future Work

As a foundational theoretical work, the paper leaves several avenues open for future research:

  • Empirical Validation: The most prominent limitation is the absence of empirical experiments. Future work must evaluate how ACVI performs in practice compared to state-of-the-art DistRL algorithms like IQN or C51.
  • The Regression Weighting Function: In ACVI, the regression step requires integrating over the frequency domain with a weighting function $w(\omega)$. Determining how to optimally choose $w(\omega)$ to efficiently capture the most relevant frequencies remains an open problem.
  • Policy Optimization: The current framework strictly tackles policy evaluation (estimating the return distribution for a fixed policy). Extending this frequency-domain approach to policy optimization—using the CVF to actively find a risk-aware optimal policy—is a critical next step for practical agent control.

Summary updated

BibTeX
@inproceedings{farahmand2019value,
  author = {Amir-massoud Farahmand},
  title = {{Value Function in Frequency Domain and the Characteristic Value Iteration Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure