Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Anytime Exploration for Multi-armed Bandits using Confidence Information.

ABSTRACT: We introduce anytime Explore-m, a pure exploration problem for multi-armed bandits (MAB) that requires making a prediction of the top-m arms at every time step. Anytime Explore-m is more practical than fixed budget or fixed confidence formulations of the top-m problem, since many applications involve a finite, but unpredictable, budget. However, the development and analysis of anytime algorithms present many challenges. We propose AT-LUCB (AnyTime Lower and Upper Confidence Bound), the first nontrivial algorithm that provably solves anytime Explore-m. Our analysis shows that the sample complexity of AT-LUCB is competitive to anytime variants of existing algorithms. Moreover, our empirical evaluation on AT-LUCB shows that AT-LUCB performs as well as or better than state-of-the-art baseline methods for anytime Explore-m.

SUBMITTER: Jun KS

PROVIDER: S-EPMC5846129 | biostudies-literature | 2016 Jun

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Anytime Exploration for Multi-armed Bandits using Confidence Information.

Jun Kwang-Sung KS Nowak Robert R

JMLR workshop and conference proceedings 20160601

We introduce anytime Explore-m, a pure exploration problem for multi-armed bandits (MAB) that requires making a prediction of the top-m arms at every time step. Anytime Explore-m is more practical than fixed budget or fixed confidence formulations of the top-m problem, since many applications involve a finite, but unpredictable, budget. However, the development and analysis of anytime algorithms present many challenges. We propose AT-LUCB (AnyTime Lower and Upper Conf ...[more]

PMID: 29541329

Similar Datasets

Optimal Query Selection Using Multi-Armed Bandits.

Project description:Query selection for latent variable estimation is conventionally performed by opting for observations with low noise or optimizing information theoretic objectives related to reducing the level of estimated uncertainty based on the current best estimate. In these approaches, typically the system makes a decision by leveraging the current available information about the state. However, trusting the current best estimate results in poor query selection when truth is far from the current estimate, and this negatively impacts the speed and accuracy of the latent variable estimation procedure. We introduce a novel sequential adaptive action value function for query selection using the multi-armed bandit (MAB) framework which allows us to find a tractable solution. For this adaptive-sequential query selection method, we analytically show: (i) performance improvement in the query selection for a dynamical system, (ii) the conditions where the model outperforms competitors. We also present favorable empirical assessments of the performance for this method, compared to alternative methods, both using Monte Carlo simulations and human-in-the-loop experiments with a brain computer interface (BCI) typing system where the language model provides the prior information.

| S-EPMC6777547 | biostudies-literature

An Analysis of the Value of Information When Exploring Stochastic, Discrete Multi-Armed Bandits.

Project description:In this paper, we propose an information-theoretic exploration strategy for stochastic, discrete multi-armed bandits that achieves optimal regret. Our strategy is based on the value of information criterion. This criterion measures the trade-off between policy information and obtainable rewards. High amounts of policy information are associated with exploration-dominant searches of the space and yield high rewards. Low amounts of policy information favor the exploitation of existing knowledge. Information, in this criterion, is quantified by a parameter that can be varied during search. We demonstrate that a simulated-annealing-like update of this parameter, with a sufficiently fast cooling schedule, leads to a regret that is logarithmic with respect to the number of arm pulls.

| S-EPMC7512671 | biostudies-literature

Multi-USV Adaptive Exploration Using Kernel Information and Residual Variance.

Project description:Using a team of robots for estimating scalar environmental fields is an emerging approach. The aim of such an approach is to reduce the mission time for collecting informative data as compared to a single robot. However, increasing the number of robots requires coordination and efficient use of the mission time to provide a good approximation of the scalar field. We suggest an online multi-robot framework m-AdaPP to handle this coordination. We test our framework for estimating a scalar environmental field with no prior information and benchmark the performance via field experiments against conventional approaches such as lawn mower patterns. We demonstrated that our framework is capable of handling a team of robots for estimating a scalar field and outperforms conventional approaches used for approximating water quality parameters. The suggested framework can be used for estimating other scalar functions such as air temperature or vegetative index using land or aerial robots as well. Finally, we show an example use case of our adaptive algorithm in a scientific study for understanding micro-level interactions.

| S-EPMC8194496 | biostudies-literature

Confidence modulates exploration and exploitation in value-based learning.

Project description:Uncertainty is ubiquitous in cognitive processing. In this study, we aim to investigate the ability agents possess to track and report the noise inherent in their mental operations, often in the form of confidence judgments. Here, we argue that humans can use uncertainty inherent in their representations of value beliefs to arbitrate between exploration and exploitation. Such uncertainty is reflected in explicit confidence judgments. Using a novel variant of a multi-armed bandit paradigm, we studied how beliefs were formed and how uncertainty in the encoding of these value beliefs (belief confidence) evolved over time. We found that people used uncertainty to arbitrate between exploration and exploitation, reflected in a higher tendency toward exploration when their confidence in their value representations was low. We furthermore found that value uncertainty can be linked to frameworks of metacognition in decision making in two ways. First, belief confidence drives decision confidence, i.e. people's evaluation of their own choices. Second, individuals with higher metacognitive insight into their choices were also better at tracing the uncertainty in their environment. Together, these findings argue that such uncertainty representations play a key role in the context of cognitive control.

| S-EPMC6505439 | biostudies-literature

Unconscious information changes decision accuracy but not confidence.

Project description:The controversial idea that information can be processed and evaluated unconsciously to change behavior has had a particularly impactful history. Here, we extend a simple model of conscious decision-making to explain both conscious and unconscious accumulation of decisional evidence. Using a novel dichoptic suppression paradigm to titrate conscious and unconscious evidence, we show that unconscious information can be accumulated over time and integrated with conscious elements presented either before or after to boost or diminish decision accuracy. The unconscious information could only be used when some conscious decision-relevant information was also present. These data are fit well by a simple diffusion model in which the rate and variability of evidence accumulation is reduced but not eliminated by the removal of conscious awareness. Surprisingly, the unconscious boost in accuracy was not accompanied by corresponding increases in confidence, suggesting that we have poor metacognition for unconscious decisional evidence.

| S-EPMC4234611 | biostudies-other

Some performance considerations when using multi-armed bandit algorithms in the presence of missing data.

Project description:When comparing the performance of multi-armed bandit algorithms, the potential impact of missing data is often overlooked. In practice, it also affects their implementation where the simplest approach to overcome this is to continue to sample according to the original bandit algorithm, ignoring missing outcomes. We investigate the impact on performance of this approach to deal with missing data for several bandit algorithms through an extensive simulation study assuming the rewards are missing at random. We focus on two-armed bandit algorithms with binary outcomes in the context of patient allocation for clinical trials with relatively small sample sizes. However, our results apply to other applications of bandit algorithms where missing data is expected to occur. We assess the resulting operating characteristics, including the expected reward. Different probabilities of missingness in both arms are considered. The key finding of our work is that when using the simplest strategy of ignoring missing data, the impact on the expected performance of multi-armed bandit strategies varies according to the way these strategies balance the exploration-exploitation trade-off. Algorithms that are geared towards exploration continue to assign samples to the arm with more missing responses (which being perceived as the arm with less observed information is deemed more appealing by the algorithm than it would otherwise be). In contrast, algorithms that are geared towards exploitation would rapidly assign a high value to samples from the arms with a current high mean irrespective of the level observations per arm. Furthermore, for algorithms focusing more on exploration, we illustrate that the problem of missing responses can be alleviated using a simple mean imputation approach.

| S-EPMC9467360 | biostudies-literature

Signal detection models as contextual bandits.

Project description:Signal detection theory (SDT) has been widely applied to identify the optimal discriminative decisions of receivers under uncertainty. However, the approach assumes that decision-makers immediately adopt the appropriate acceptance threshold, even though the optimal response must often be learned. Here we recast the classical normal-normal (and power-law) signal detection model as a contextual multi-armed bandit (CMAB). Thus, rather than starting with complete information, decision-makers must infer how the magnitude of a continuous cue is related to the probability that a signaller is desirable, while simultaneously seeking to exploit the information they acquire. We explain how various CMAB heuristics resolve the trade-off between better estimating the underlying relationship and exploiting it. Next, we determined how naive human volunteers resolve signal detection problems with a continuous cue. As anticipated, a model of choice (accept/reject) that assumed volunteers immediately adopted the SDT-predicted acceptance threshold did not predict volunteer behaviour well. The Softmax rule for solving CMABs, with choices based on a logistic function of the expected payoffs, best explained the decisions of our volunteers but a simple midpoint algorithm also predicted decisions well under some conditions. CMABs offer principled parametric solutions to solving many classical SDT problems when decision-makers start with incomplete information.

| S-EPMC10282591 | biostudies-literature

Long-lasting antifouling coating from multi-armed polymer.

Project description:We describe a new antifouling surface coating, based on aggregation of a short amphiphilic four-armed PEG-dopamine polymer into particles and on surface binding by catechol chemistry. An unbroken and smooth polymeric coating layer with an average thickness of approximately 4 ?m was formed on top of titanium oxide surfaces by a single step reaction. Coatings conferred excellent resistance to protein adhesion. Cell attachment was completely prevented for at least eight weeks, although the membranes themselves did not appear to be intrinsically cytotoxic. When linear PEG or four-armed PEG of higher molecular weight were used, the resulting coatings were inferior in thickness and in preventing protein adhesion. This coating method has potential applicability for biomedical devices susceptible to fouling after implantation.

| S-EPMC3775852 | biostudies-literature

The Confidence Information Ontology: a step towards a standard for asserting confidence in annotations.

Project description:Biocuration has become a cornerstone for analyses in biology, and to meet needs, the amount of annotations has considerably grown in recent years. However, the reliability of these annotations varies; it has thus become necessary to be able to assess the confidence in annotations. Although several resources already provide confidence information about the annotations that they produce, a standard way of providing such information has yet to be defined. This lack of standardization undermines the propagation of knowledge across resources, as well as the credibility of results from high-throughput analyses. Seeded at a workshop during the Biocuration 2012 conference, a working group has been created to address this problem. We present here the elements that were identified as essential for assessing confidence in annotations, as well as a draft ontology--the Confidence Information Ontology--to illustrate how the problems identified could be addressed. We hope that this effort will provide a home for discussing this major issue among the biocuration community. Tracker URL: https://github.com/BgeeDB/confidence-information-ontology Ontology URL: https://raw.githubusercontent.com/BgeeDB/confidence-information-ontology/master/src/ontology/cio-simple.obo

| S-EPMC4425939 | biostudies-literature

Familywise error control in multi-armed response-adaptive trials.

Project description:Response-adaptive designs allow the randomization probabilities to change during the course of a trial based on cumulated response data so that a greater proportion of patients can be allocated to the better performing treatments. A major concern over the use of response-adaptive designs in practice, particularly from a regulatory viewpoint, is controlling the type I error rate. In particular, we show that the naïve z-test can have an inflated type I error rate even after applying a Bonferroni correction. Simulation studies have often been used to demonstrate error control but do not provide a guarantee. In this article, we present adaptive testing procedures for normally distributed outcomes that ensure strong familywise error control by iteratively applying the conditional invariance principle. Our approach can be used for fully sequential and block randomized trials and for a large class of adaptive randomization rules found in the literature. We show there is a high price to pay in terms of power to guarantee familywise error control for randomization schemes with extreme allocation probabilities. However, for proposed Bayesian adaptive randomization schemes in the literature, our adaptive tests maintain or increase the power of the trial compared to the z-test. We illustrate our method using a three-armed trial in primary hypercholesterolemia.

| S-EPMC6739232 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data