# A Cover Time Study of a non-Markovian Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 65 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 13 of 13)

- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Eigenoption Discovery through the Deep Successor Representation](https://mlsanity.com/paper/1710.11089/) (2017)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Diversity-Driven Exploration Strategy for Deep Reinforcement Learning](https://mlsanity.com/paper/1802.04564/) (2018)
- [Discovering Options for Exploration by Minimizing Cover Time](https://mlsanity.com/paper/1903.00606/) (2019)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Context-Dependent Upper-Confidence Bounds for Directed Exploration](https://mlsanity.com/paper/1811.06629/) (2018)

## Abstract (arXiv)

Given a traversal algorithm, cover time is the expected number of steps needed to visit all nodes in a given graph. A smaller cover time means a higher exploration efficiency of traversal algorithm. Although random walk algorithms have been studied extensively in the existing literature, there has been no cover time result for any non-Markovian method. In this work, we stand on a theoretical perspective and show that the negative feedback strategy (a count-based exploration method) is better than the naive random walk search. In particular, the former strategy can locally improve the search efficiency for an arbitrary graph. It also achieves smaller cover times for special but important graphs, including clique graphs, tree graphs, etc. Moreover, we make connections between our results and reinforcement learning literature to give new insights on why classical UCB and MCTS algorithms are so useful. Various numerical results corroborate our theoretical findings.