Managing Uncertainty within KTD

Matthieu Geist, Olivier PietquinActive Learning and Experimental Design @ AISTATS 2011 · OpenReview

Introduction

Reinforcement Learning (RL) agents are perpetually caught in the exploration-exploitation dilemma: should they exploit known high-value actions or explore new ones to refine their understanding of the environment? Traditional strategies like $\epsilon$-greedy are "blind," exploring randomly without regard for where the agent's knowledge is most deficient. This paper introduces a method to quantify and leverage uncertainty within the Kalman Temporal Differences (KTD) framework, enabling "informed" exploration that significantly accelerates learning in complex, continuous state spaces.

Methodology

The core of this approach lies in treating RL as a statistical filtering problem. By building upon the KTD framework, the authors maintain a second-order statistical representation of the value function's parameters.

  1. State-Space Formulation: The weights of the value function approximation are modeled as a hidden state to be tracked, with rewards serving as observations.
  2. Kalman Filtering & Unscented Transform (UT): A Kalman filter maintains the mean and covariance of these parameters. The UT is employed to propagate this uncertainty through the non-linear Bellman equations, avoiding the need for complex derivatives.
  3. Uncertainty-Aware Policies: The resulting variance ($\sigma^2$) is used to drive several novel exploration strategies, including Active KTD-Q (sampling actions proportional to uncertainty), Confident-greedy (using upper confidence bounds), and Thompson Sampling.
Uncertainty computation in the KTD framework.

A key insight is that uncertainty is a "free" byproduct of the KTD framework's second-order statistical tracking, rather than an expensive additional computation. This allows for model-free uncertainty estimation that scales to large problems.

Experimental Evaluation

The proposed methods were evaluated across three benchmarks:

  • Inverted Pendulum: A classic control task testing off-policy convergence speed.
  • 10-Armed Bandit: A standard testbed for comparing exploration policies.
  • Spoken Dialogue Management: A real-world application involving a tourism information system, where the agent manages interactions with simulated users.

Results and Discussion

The empirical results demonstrate that informed exploration consistently outperforms uninformed baselines. In the Inverted Pendulum task, Active KTD-Q nearly doubled the learning speed in the initial 100 episodes compared to standard random exploration.

Performance comparison on the Inverted Pendulum task showing steps per episode for KTD-Q, Q-learning, and active KTD-Q.

In the dialogue management task, the Bonus-greedy policy achieved faster convergence and greater stability than uninformed baselines, matching state-of-the-art batch algorithms like LSPI while requiring fewer transitions. This highlights the sample efficiency of KTD-SARSA, particularly in data-scarce scenarios where numerical stability is often an issue.

Conclusion

This work demonstrates that maintaining uncertainty in value function approximation is both feasible and highly beneficial for RL. By moving beyond blind exploration, agents can reach optimal policies much faster. Future work will focus on establishing formal convergence proofs and addressing the computational complexity of matrix inversions in high-dimensional parameter spaces, such as those found in deep learning.

Summary updated

BibTeX
@inproceedings{geist2011managing,
  author = {Matthieu Geist and Olivier Pietquin},
  title = {{Managing Uncertainty within KTD}},
  booktitle = {Active Learning and Experimental Design @ AISTATS},
  year = {2011},
  url = {https://openreview.net/forum?id=ufqXx-qvxGPH},
}
Figure