# Context-Dependent Upper-Confidence Bounds for Directed Exploration

arXiv: https://arxiv.org/abs/1811.06629 · HTML: https://mlsanity.com/paper/1811.06629/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2018.

## Built on by (most cited first, 3 of 3)

- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Value Bonuses using Ensemble Errors for Exploration in Reinforcement Learning](https://mlsanity.com/paper/2602.12375/) (2026)
- [A Cover Time Study of a non-Markovian Algorithm](https://mlsanity.com/paper/2306.04902/) (2023)

## Abstract (arXiv)

Directed exploration strategies for reinforcement learning are critical for learning an optimal policy in a minimal number of interactions with the environment. Many algorithms use optimism to direct exploration, either through visitation estimates or upper confidence bounds, as opposed to data-inefficient strategies like ε-greedy that use random, undirected exploration. Most data-efficient exploration methods require significant computation, typically relying on a learned model to guide exploration. Least-squares methods have the potential to provide some of the data-efficiency benefits of model-based approaches -- because they summarize past interactions -- with the computation closer to that of model-free approaches. In this work, we provide a novel, computationally efficient, incremental exploration strategy, leveraging this property of least-squares temporal difference learning (LSTD). We derive upper confidence bounds on the action-values learned by LSTD, with context-dependent (or state-dependent) noise variance. Such context-dependent noise focuses exploration on a subset of variable states, and allows for reduced exploration in other states. We empirically demonstrate that our algorithm can converge more quickly than other incremental exploration strategies using confidence estimates on action-values.