Active Exploration via Experiment Design in Markov Chains
- URL: http://arxiv.org/abs/2206.14332v1
- Date: Wed, 29 Jun 2022 00:04:40 GMT
- Title: Active Exploration via Experiment Design in Markov Chains
- Authors: Mojm\'ir Mutn\'y and Tadeusz Janik and Andreas Krause
- Abstract summary: A key challenge in science and engineering is to design experiments to learn about some unknown quantity of interest.
We propose an algorithm that efficiently selects policies whose measurement allocation converges to the optimal one.
In addition to our theoretical analysis, we showcase our framework on applications in ecological surveillance and pharmacology.
- Score: 86.41407938210193
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 -- \textsc{markov-design} -- that efficiently selects policies
whose measurement allocation \emph{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.
Related papers
- Globally-Optimal Greedy Experiment Selection for Active Sequential
Estimation [1.1530723302736279]
We study the problem of active sequential estimation, which involves adaptively selecting experiments for sequentially collected data.
The goal is to design experiment selection rules for more accurate model estimation.
We propose a class of greedy experiment selection methods and provide statistical analysis for the maximum likelihood.
arXiv Detail & Related papers (2024-02-13T17:09:29Z) - Optimistic Active Exploration of Dynamical Systems [52.91573056896633]
We develop an algorithm for active exploration called OPAX.
We show how OPAX can be reduced to an optimal control problem that can be solved at each episode.
Our experiments show that OPAX is not only theoretically sound but also performs well for zero-shot planning on novel downstream tasks.
arXiv Detail & Related papers (2023-06-21T16:26:59Z) - Task-specific experimental design for treatment effect estimation [59.879567967089145]
Large randomised trials (RCTs) are the standard for causal inference.
Recent work has proposed more sample-efficient alternatives to RCTs, but these are not adaptable to the downstream application for which the causal effect is sought.
We develop a task-specific approach to experimental design and derive sampling strategies customised to particular downstream applications.
arXiv Detail & Related papers (2023-06-08T18:10:37Z) - GFlowNets for AI-Driven Scientific Discovery [74.27219800878304]
We present a new probabilistic machine learning framework called GFlowNets.
GFlowNets can be applied in the modeling, hypotheses generation and experimental design stages of the experimental science loop.
We argue that GFlowNets can become a valuable tool for AI-driven scientific discovery.
arXiv Detail & Related papers (2023-02-01T17:29:43Z) - Evaluating Guiding Spaces for Motion Planning [2.384084215091134]
We define the emphmotion planning guiding space, which encapsulates many seemingly distinct prior works under the same framework.
We also suggest an information theoretic method to evaluate guided planning which places the focus on the quality of the resulting biased sampling.
arXiv Detail & Related papers (2022-10-16T21:17:51Z) - Biological Sequence Design with GFlowNets [75.1642973538266]
Design of de novo biological sequences with desired properties often involves an active loop with several rounds of molecule ideation and expensive wet-lab evaluations.
This makes the diversity of proposed candidates a key consideration in the ideation phase.
We propose an active learning algorithm leveraging uncertainty estimation and the recently proposed GFlowNets as a generator of diverse candidate solutions.
arXiv Detail & Related papers (2022-03-02T15:53:38Z) - Reinforcement Learning based Sequential Batch-sampling for Bayesian
Optimal Experimental Design [1.6249267147413522]
Sequential design of experiments (SDOE) is a popular suite of methods, that has yielded promising results in recent years.
In this work, we aim to extend the SDOE strategy, to query the experiment or computer code at a batch of inputs.
A unique capability of the proposed methodology is its ability to be applied to multiple tasks, for example optimization of a function, once its trained.
arXiv Detail & Related papers (2021-12-21T02:25:23Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
We investigate the active pure exploration problem in Markov Decision Processes.
Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
arXiv Detail & Related papers (2021-06-05T09:16:28Z) - Task-Optimal Exploration in Linear Dynamical Systems [29.552894877883883]
We study task-guided exploration and determine what precisely an agent must learn about their environment in order to complete a task.
We provide instance- and task-dependent lower bounds which explicitly quantify the difficulty of completing a task of interest.
We show that it optimally explores the environment, collecting precisely the information needed to complete the task, and provide finite-time bounds guaranteeing that it achieves the instance- and task-optimal sample complexity.
arXiv Detail & Related papers (2021-02-10T01:42:22Z) - Olympus: a benchmarking framework for noisy optimization and experiment
planning [0.0]
Experiment planning strategies based on off-the-shelf optimization algorithms can be employed in fully autonomous research platforms.
It is unclear how their performance would translate to noisy, higher-dimensional experimental tasks.
We introduce Olympus, a software package that provides a consistent and easy-to-use framework for benchmarking optimization algorithms.
arXiv Detail & Related papers (2020-10-08T17:51:51Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.