Q-Measure-Learning
Relevant paper:
- Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergence
- Shengbo Wang
- Some slides for this work
Q-measure-learning is an online method for continuous-state reinforcement learning that represents a smoothed Bellman fixed point through a signed empirical measure supported on visited state-action pairs. The measure is updated along a single trajectory of data generated by a behavior policy, and an action-value estimate is reconstructed by normalized kernel integration.
1. Motivation and construction
We provide a brief overview of Q-measure-learning, which learns a measure via a weighted empirical process, rather than a state-action value function. This enables efficient updates while allowing fast computation of the state-action value estimates.
Why learn a measure rather than a function?
In a continuous state space, the optimal action-value function $Q^\star(x,a)$ is an infinite-dimensional object. A tabular Q-learning update changes one state-action entry, but there is no finite table with an entry for every pair $(x,a)$. A conventional function-approximation method addresses this by selecting a parameterized class and updating its parameters. This class of algorithms typically requires careful selection of the function class and optimization method to be provably stable.
Q-measure-learning takes a different route: it stores scalar Bellman target estimates only at state-action pairs visited by the behavior trajectory, and uses them to form the Q-measure. It only performs spatial generalization using a normalized kernel integration later when the Q-function estimate is needed. This leads to a simple and efficient algorithm that is provably convergent under mild conditions.
Kernel-smoothed Bellman operator and q-function
First, we introduce the smoothed Bellman operator and $q^*$-function. Let $\mathbb{X}$ and $\mathbb{A}$ denote the state and action spaces, set $\mathbb{Z}:=\mathbb{X}\times\mathbb{A}$, and write $Z_n=(X_n,A_n)$, where $A_n$ is selected by a behavior policy $\pi_b(\cdot\mid X_n)$ and $X_{n+1}\sim P(\cdot\mid X_n,A_n)$. The Bellman optimality operator is
\[\mathcal{T}[q](x,a) = r(x,a) +\gamma\int_{\mathbb{X}} \sup_{a'\in\mathbb{A}}q(x',a') P(dx'\mid x,a).\]As motivated earlier, we want to learn a Q-measure and reconstruct the Q-function via normalized kernel integration. To achieve this, we consider a positive kernel on the state-action space, such as the Gaussian kernel
\[\kappa_\sigma(z,u)=\exp\!\left(-\frac{\lVert z-u\rVert^2}{2\sigma^2}\right),\]where $\sigma > 0$ is the bandwidth.
Let $\mu$ be a reference measure on $\mathbb{Z}$. We will choose $\mu=\mu_b$, the stationary distribution of the behavior Markov chain $(X_n,A_n)$. In the Q-measure-learning algorithm, it is estimated by the empirical occupation measure of the behavior chain. Define the normalized kernel operator
\[K_{\mu,\sigma}[f](z) = \frac{\int_{\mathbb{Z}}\kappa_\sigma(z,u)f(u)\,\mu(du)} {\int_{\mathbb{Z}}\kappa_\sigma(z,u)\,\mu(du)}.\]For a fixed bandwidth $\sigma > 0$, the Q-measure-learning algorithm aims to learn the unique fixed point
\[q_\sigma^\star=K_{\mu_b,\sigma}\!\left[\mathcal{T}[q_\sigma^\star]\right]\]rather than directly targeting the original Bellman fixed point $Q^\star=\mathcal{T}[Q^\star]$. Importantly, we note that if $\sigma \downarrow 0$, the normalized kernel operator converges to the identity. So, we should expect that $q_\sigma^\star$ approximates $Q^\star$ for small $\sigma$.
The Q-measure representation
Define the Q-measure associated with the smoothed fixed point by
\[\nu_\sigma^\star(du)=\mathcal{T}[q_\sigma^\star](u)\,\mu_b(du), \qquad u\in\mathbb{Z}.\]Then the fixed point $q_\sigma^\star$ is represented as a normalized kernel integral
\[q_\sigma^\star(z) = \Phi_{\mu_b,\sigma}[\nu_\sigma^\star](z) := \frac{\int_{\mathbb{Z}}\kappa_\sigma(z,u)\,\nu_\sigma^\star(du)} {\int_{\mathbb{Z}}\kappa_\sigma(z,u)\,\mu_b(du)},\]where the numerator is the Q-measure smoothed by the kernel $\kappa_\sigma$. The advantage of approximating the Q-measure can be seen from this symmetric ratio representation: we can approximate $\mu_b$ using the empirical measure of the Markov chain, so we might also be able to approximate $\nu_\sigma^\star$ using a similar empirical measure construction. This leads to the Q-measure-learning algorithm, which we will illustrate next.
The Q-measure-learning algorithm
At iteration $n$, maintain a probability measure $\mu_n$ on $\mathbb{Z}$, a signed measure $\nu_n$. Compute the current estimate $q_n=\Phi_{\mu_n,\sigma}[\nu_n]$. We consider the following recursion:
At $Z_n=(X_n,A_n)$, observe $R_{n+1}$ and $X_{n+1}$, then draw $A_{n+1}\sim\pi_b(\cdot\mid X_{n+1})$.
Form the Q-learning target
\[Y_{n+1} =R_{n+1} +\gamma\sup_{a'\in\mathbb{A}}q_n(X_{n+1},a'),\]where $q_n(z)=\Phi_{\mu_n,\sigma} [\nu_n] (z)$.
Update the Q-measure:
\[\nu_{n+1}=(1-\alpha_{n+1})\nu_n +\alpha_{n+1}Y_{n+1}\delta_{Z_n}.\]Update the empirical reference measure:
\[\mu_{n+1}=(1-\beta_{n+1})\mu_n +\beta_{n+1}\delta_{Z_{n+1}},\]and return to step 1.
This algorithm can be viewed as a two-time-scale stochastic approximation algorithm for the optimal Q-measure and the stationary distribution $\mu_b$. However, since both $\mu_n$ and $\nu_n$ are measures, the recursion is not directly implementable. The next section shows how to realize the recursion as simple array operations and kernel evaluations.
Efficient implementation
Writing the measures as weighted atomic sums,
\[\mu_n=\sum_{k=0}^{n}u_{n,k}\delta_{Z_k}, \qquad \nu_n=\sum_{k=1}^{n}W_{n,k}\delta_{Z_{k-1}},\]turns the above abstract recursion into two array operations:
\[\begin{aligned} u_{n+1,k}&=(1-\beta_{n+1})u_{n,k}, &u_{n+1,n+1}&=\beta_{n+1},\\ W_{n+1,k}&=(1-\alpha_{n+1})W_{n,k}, &W_{n+1,n+1}&=\alpha_{n+1}Y_{n+1}. \end{aligned}\]Here, to compute $Y_{n+1}$, we can evaluate $q_n$ using the weights ${W_{n,k},u_{n,k}:k=1\dots n}$:
\[q_n(z)= \frac{\sum_{k=1}^{n}W_{n,k}\kappa_\sigma(z,Z_{k-1})} {\sum_{k=0}^{n}u_{n,k}\kappa_\sigma(z,Z_k)}.\]This is the weight-based implementation of the Q-measure-learning algorithm.
Thus, running this procedure requires neither a state-action grid nor a kernel-matrix inversion. The method stores $O(n)$ visited pairs and weights. For finite $\mathbb{A}$, evaluating the target over all next actions costs $O(\lvert\mathbb{A}\rvert n)$ kernel operations per iteration; for continuous $\mathbb{A}$, the supremum can be replaced by a numerical action-optimization step.
2. Why the recursion converges to $\nu^\star_\sigma$ and $q^\star_\sigma$
Suppose that we have access to the stationary distribution $\mu_b$. Then, replacing the random normalization $\mu_n$ by $\mu_b$, the Q-measure-learning algorithm induces a stochastic approximation (SA) iterate for the $q$-function of the form
\[\bar q_{n+1} = \bar q_n +\alpha_{n+1}\bigl(K_{\mu_b,\sigma}\!\left[\mathcal{T}[\bar q_n]\right]-\bar q_n\bigr) +\alpha_{n+1}\varepsilon_{n+1}.\]The mean-field ODE for this SA update is governed by the vector field $K_{\mu_b,\sigma}\circ\mathcal{T}-I$. Because $K_{\mu_b,\sigma}\circ\mathcal{T}$ is a $\gamma$-contraction, the fixed point $q_\sigma^\star$ of the mean-field ODE is globally stable. Thus, one would expect the iterates $\bar q_n\rightarrow q^\star_\sigma$ under the Robbins-Monro step size.
On the other hand, since the behavior chain is uniformly ergodic, $\mu_n\rightarrow\mu_b$ almost surely. Therefore, $q_n$ should be close to $\bar q_n$ and should also converge to $q_\sigma^\star$. This in turn implies the convergence of $\nu_n$ to $\nu_\sigma^\star$ in a kernel-induced measure metric.
A one-dimensional illustration
We visualize the convergence of the Q-measure recursion through the reconstructed $q$-function. For visual simplicity, we choose the singleton action space $\mathbb{A}={a_0}$ and suppress the fixed action coordinate, writing $q(x)$ for $q(x,a_0)$. Consider the following discounted MDP:
- State space: $\mathbb{X}=[0,1]$.
- Discount factor: $\gamma=0.75$.
State transition: the next state is independent of the current state and uniformly distributed,
\[X_{n+1}\mid X_n=x\sim\operatorname{Unif}[0,1], \qquad P(dy\mid x)=\mathbf 1_{[0,1]}(y)\,dy.\]- Reward: deterministic conditional on the current state, $R_{n+1}=r(X_n)$.
To make the true Bellman fixed point known exactly, first define
\[\begin{aligned} Q^\star(x)={}&0.40 +0.48\exp\!\left[-\left(\frac{x-0.22}{0.075}\right)^2\right] -0.36\exp\!\left[-\left(\frac{x-0.56}{0.095}\right)^2\right]\\ &+0.20\sin(2\pi x)+0.16x. \end{aligned}\]Its mean is $\bar Q^\star:=\int_0^1Q^\star(u)\,du\approx0.483$. Choose the reward to be
\[r(x)=Q^\star(x)-\gamma\bar Q^\star.\]Then, because the transition is uniform,
\[\mathcal{T}[Q^\star](x) =r(x)+\gamma\int_0^1Q^\star(y)\,dy =Q^\star(x),\]so the displayed $Q^\star$ is the exact Bellman fixed point.
On the other hand, for a selected bandwidth, the limiting small-q function and Q-measure are computed from
\[q_\sigma^\star=K_{\mu_b,\sigma}[r]+\gamma\int_0^1q_\sigma^\star(y)\,dy, \qquad \nu_\sigma^\star(du) =\left(r(u)+\gamma\int_0^1q_\sigma^\star(y)\,dy\right)du,\]with $\mu_b$ equal to the uniform distribution. The empirical iterates use one fixed realization of the uniform transition law and the step sizes $\alpha_n=n^{-0.9}$ and $\beta_n=1/(n+1)$.
Figure 1. The cumulative mass of $\nu_n$ approaches that of $\nu_\sigma^\star$, while $q_n$, reconstructed from $\nu_n$, approaches $q_\sigma^\star$. The learned cumulative mass function is a step function, with each vertical jump equal to the corresponding atomic weight at time $n$.
3. Smoothed versus original Bellman fixed points
Convergence to the smoothed fixed point does not by itself imply exact recovery of the original Bellman fixed point. The total error decomposes as
\[\lVert q_n-Q^\star\rVert_\infty \leq \underbrace{\lVert q_n-q_\sigma^\star\rVert_\infty}_{\text{learning error}} + \underbrace{\lVert q_\sigma^\star-Q^\star\rVert_\infty}_{\text{smoothing error}}.\]The first term vanishes as $n$ grows. The second is deterministic and controlled by the bandwidth.
From the two fixed-point identities and non-expansiveness of $K_{\mu_b,\sigma}$,
\[\lVert Q^\star-q_\sigma^\star\rVert_\infty \leq \frac{1}{1-\gamma} \lVert Q^\star-K_{\mu_b,\sigma}[Q^\star]\rVert_\infty.\]A smaller bandwidth makes the smoothing operator more local and hence closer to the identity. Under $\alpha$-Hölder regularity and coverage conditions, this deterministic error is of order $\sigma^\alpha$. For finite $n$, however, a very narrow kernel uses fewer nearby observations and can make the reconstructed $q_n$ rougher.
Figure 2. The upper panel compares the $Q^\star$ reference curve with the fixed point $q_\sigma^\star$ targeted by the Q-measure-learning algorithm. The lower panel computes the sup-norm and root-mean-square errors. The two circular markers and the vertical guide correspond to the selected $\sigma$.