Value Function in Frequency Domain and the Characteristic Value Iteration Algorithm

Paper: Short version; Extended version
Poster

Informal Summary

Brief: We can develop a distributional RL framework through the use of characteristic function. It is an alternative to representing the uncertainty of returns by probability distribution functions.

Longer: A conventional RL agent maintains the expected value of returns, i.e., long-term reward. But sometimes we would like to know more than the expected value of returns, for example when we want to deal with risk.
How can we represent something more than the expected return? One approach is to represent the probability distribution function of return. This has already been explored.
I show that you can represent the uncertainty of return using its characteristic function, which is the Fourier transform of its probability distribution. I call this Characteristic Value Function (CVF). CVF satisfies a Bellman equation, which is multiplicative instead of additive. And the Bellman operator is a contraction, and one can obtain CVF by an iterative method similar to Value Iteration, which is called Characteristic Value Iteration.

Abstract

This paper considers the problem of estimating the distribution of returns in reinforcement learning (i.e., distributional RL problem). It presents a new representational framework to maintain the uncertainty of returns and provides mathematical tools to compute it.
We show that instead of representing a probability distribution function of returns, one can represent their characteristic function instead, the Fourier transform of their distribution. We call the new representation Characteristic Value Function (CVF), which can be interpreted as the frequency domain representation of the probability distribution of returns.
We show that the CVF satisfies a Bellman-like equation, and its corresponding Bellman operator is contraction with respect to certain metrics. The contraction property allows us to devise an iterative procedure to compute the CVF, which we call Characteristic Value Iteration (CVI). We analyze CVI and its approximate variant and show how approximation errors affect the quality of computed CVF.