# Active Exploration via Experiment Design in Markov Chains

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 53 references that are in the map.
- First posted on arXiv 29 Jun 2022.

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

- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Deep Adaptive Design: Amortizing Sequential Bayesian Experimental Design](https://mlsanity.com/paper/2103.02438/) (2021)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [Information Directed Reward Learning for Reinforcement Learning](https://mlsanity.com/paper/2102.12466/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Inverse Reinforcement Learning in Contextual MDPs](https://mlsanity.com/paper/1905.09710/) (2019)
- [Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier](https://mlsanity.com/paper/2010.08999/) (2020)
- [Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2205.13627/) (2022)
- [Stochastic Online Shortest Path Routing: The Value of Feedback](https://mlsanity.com/paper/1309.7367/) (2013)
- [Sensing Cox Processes via Posterior Sampling and Positive Bases](https://mlsanity.com/paper/2110.11181/) (2021)

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

- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Optimistic Active Exploration of Dynamical Systems](https://mlsanity.com/paper/2306.12371/) (2023)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning](https://mlsanity.com/paper/2511.22640/) (2025)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Provable Maximum Entropy Manifold Exploration via Diffusion Models](https://mlsanity.com/paper/2506.15385/) (2025)
- [Efficient Tail-Aware Generative Optimization via Flow Model Fine-Tuning](https://mlsanity.com/paper/2602.16796/) (2026)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [Transition Constrained Bayesian Optimization via Markov Decision Processes](https://mlsanity.com/paper/2402.08406/) (2024)
- [Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction](https://mlsanity.com/paper/2407.13364/) (2024)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [The Catechol Benchmark: Time-series Solvent Selection Data for Few-shot Machine Learning](https://mlsanity.com/paper/2506.07619/) (2025)
- [Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design](https://mlsanity.com/paper/2506.09508/) (2025)
- [Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2602.06769/) (2026)
- [Practical Path-based Bayesian Optimization](https://mlsanity.com/paper/2312.00622/) (2023)
- [BALLAST: Bayesian Active Learning with Look-ahead Amendment for Sea-drifter Trajectories under Spatio-Temporal Vector Fields](https://mlsanity.com/paper/2509.26005/) (2025)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Efficient Personalization of Generative Models via Optimal Experimental Design](https://mlsanity.com/paper/2512.19057/) (2025)

## Abstract (arXiv)

A key challenge in science and engineering is to design experiments to learn about some unknown quantity of interest. Classical experimental design optimally allocates the experimental budget to maximize a notion of utility (e.g., reduction in uncertainty about the unknown quantity). We consider a rich setting, where the experiments are associated with states in a em Markov chain, and we can only choose them by selecting a em policy controlling the state transitions. This problem captures important applications, from exploration in reinforcement learning to spatial monitoring tasks. We propose an algorithm -- textscmarkov-design -- that efficiently selects policies whose measurement allocation provably converges to the optimal one. The algorithm is sequential in nature, adapting its choice of policies (experiments) informed by past measurements. In addition to our theoretical analysis, we showcase our framework on applications in ecological surveillance and pharmacology.