mlsanityData to 7 Oct 2026

Active Exploration via Experiment Design in Markov Chains

arXiv 2206.14332 ↗First posted 29 Jun 2022cs.LG stat.ME stat.MLcited by 19

Not on the map. Why?

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.

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

Builds on

17 of 53 references.

References · 17

  1. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  2. 2020Coresets via Bilevel Optimization for Continual Learning and Streamingcited by 191
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2021Deep Adaptive Design: Amortizing Sequential Bayesian Experimental Designcited by 103
  5. 2021Reward is enough for convex MDPscited by 82
  6. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  7. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  8. 2019Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspacescited by 73
  9. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  10. 2019Active Exploration in Markov Decision Processescited by 27
  11. 2021Information Directed Reward Learning for Reinforcement Learningcited by 24
  12. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
5 more
  1. 2019Inverse Reinforcement Learning in Contextual MDPscited by 12
  2. 2020Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barriercited by 11
  3. 2022Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spacescited by 9
  4. 2013Stochastic Online Shortest Path Routing: The Value of Feedbackcited by 6
  5. 2021Sensing Cox Processes via Posterior Sampling and Positive Basescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 4; 2025: 6; 2026: 3.

19 papers.

Sort:

By area:

  1. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  2. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  3. 2023Submodular Reinforcement Learningcited by 23
  4. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  5. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  6. 2025Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuningcited by 15
  7. 2025Provable Maximum Entropy Manifold Exploration via Diffusion Modelscited by 12
  8. 2024Transition Constrained Bayesian Optimization via Markov Decision Processescited by 7
  9. 2024Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstractioncited by 6
  10. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  11. 2026Efficient Tail-Aware Generative Optimization via Flow Model Fine-Tuningcited by 6
  12. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
7 more
  1. 2025The Catechol Benchmark: Time-series Solvent Selection Data for Few-shot Machine Learningcited by 3
  2. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  3. 2023Practical Path-based Bayesian Optimizationcited by 2
  4. 2026Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilitiescited by 2
  5. 2025BALLAST: Bayesian Active Learning with Look-ahead Amendment for Sea-drifter Trajectories under Spatio-Temporal Vector Fieldscited by 1
  6. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  7. 2025Efficient Personalization of Generative Models via Optimal Experimental Designcited by 0