We show how an ensemble of -functions can be leveraged for more effective exploration in deep reinforcement learning. We build on well established algorithms from the bandit setting, and adapt them to the -learning setting. We propose an exploration strategy based on upper-confidence bounds (UCB). Our experimen…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,982 papers · 148 categories
Trend · papers per month
48 results for “UCB strategies”
A meta-UCB method combines stochastic bandit algorithms.
problem Combining multiple stochastic bandit algorithms efficiently.
method Meta-UCB procedure solving an N-armed bandit problem.
result Final regret depends only on the best base algorithm's regret.
RandUCB combines UCB and TS for optimal bandit performance.
problem Optimizing decision-making in uncertain environments with limited feedback.
method Randomized UCB algorithm using confidence intervals.
result Achieves minimax-optimal regret in various bandit settings.
I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds…
Recently, there has been rising interest in Bayesian optimization -- the optimization of an unknown function with assumptions usually expressed by a Gaussian Process (GP) prior. We study an optimization strategy that directly uses an estimate of the argmax of the function. This strategy offers both practical and theore…
Proposes EE-Net for neural exploration in contextual bandits.
problem Exploitation-Exploration tradeoff in contextual bandits.
method Uses two neural networks: Exploitation and Exploration, to learn reward function and adaptively explore.
result Achieves regret and outperforms existing methods.
A new decentralized policy for multi-agent MAB problems outperforms random communication.
problem Solving multi-agent multi-armed bandit problems efficiently.
method UCB strategy for individual option selection and communication strategy based on neighbor exploration potential.
result The proposed policy significantly outperforms random communication strategies.
Efficient algorithms for second-price auctions with action-dependent censoring.
problem Sequential bidding strategies for repeated auctions with incomplete information.
method Proposed novel UCB-like algorithms for second-price auctions in a stochastic setting.
result Significant improvement in worst-case regret, especially for low item values.
A new method selects algorithms and optimizes their hyper-parameters efficiently.
problem Redundant hyper-parameter search space in AutoML.
method Cascaded algorithm selection and hyper-parameter optimization with ER-UCB bandit.
result ER-UCB strategy achieves optimal regret bound for algorithm selection.
New findings show many popular bandit algorithms are unstable, contradicting minimax optimality.
problem Challenges in statistical inference from bandit algorithms due to adaptive, non-i.i.d. nature.
method Analysis of stability properties of optimism-based bandit algorithms.
result Widely used minimax-optimal UCB-style algorithms are unstable.
This paper optimizes attacks on stochastic bandits and proposes defenses against them.
problem Optimizing adversarial attacks on stochastic bandit algorithms.
method Designs optimal attack strategies and proposes defense algorithms.
result Optimal attack strategies and defense algorithms achieve near perfect performance.
Profitable Banditsstat.ML
Originally motivated by default risk management applications, this paper investigates a novel problem, referred to as the profitable bandit problem here. At each step, an agent chooses a subset of the K possible actions. For each action chosen, she then receives the sum of a random number of rewards. Her objective is t…
Classic bandit algorithms are robust to strategic manipulation as long as the total budget is small compared to the time horizon.
problem Behavior of stochastic bandit algorithms under strategic manipulation by self-interested arms.
method Analysis of three popular bandit algorithms: UCB, ε-Greedy, and Thompson Sampling.
result Regret upper bound of O(max{B, KlnT}) for all three algorithms under arbitrary adaptive manipulation.
Improved algorithm for Lipschitz bandit optimization with reduced complexity.
problem Efficiently solving the Lipschitz bandit optimization problem.
method Tree UCB-Hoeffding algorithm with adaptive partitions and tree-based search strategy.
result Achieves the regret lower bound up to a logarithmic factor with computational cost.
The exploration/exploitation (E/E) dilemma arises naturally in many subfields of Science. Multi-armed bandit problems formalize this dilemma in its canonical form. Most current research in this field focuses on generic solutions that can be applied to a wide range of problems. However, in practice, it is often the case…
The paper considers the problem of global optimization in the setup of stochastic process bandits. We introduce an UCB algorithm which builds a cascade of discretization trees based on generic chaining in order to render possible his operability over a continuous domain. The theoretical framework applies to functions u…
A new algorithm for better decision-making in recommendation systems.
problem Stochastic multi-armed bandit problem and cold start problem in recommender systems.
method Proposes Hellinger-UCB, a variant of UCB algorithm using squared Hellinger distance.
result Hellinger-UCB reaches the theoretical lower bound and outperforms other algorithms in practical applications.
In many scientific and engineering applications, we are tasked with the maximisation of an expensive to evaluate black box function . Traditional settings for this problem assume just the availability of this single function. However, in many cases, cheap approximations to may be obtainable. For example, the exp…
In this paper, we consider the challenge of maximizing an unknown function f for which evaluations are noisy and are acquired with high cost. An iterative procedure uses the previous measures to actively select the next estimation of f which is predicted to be the most useful. We focus on the case where the function ca…
UCB-V algorithm improves on UCB for MAB problems with variance estimates.
problem Optimizing arm selection in MAB problems with variance information.
method Asymptotic and high probability analysis of UCB-V algorithm.
result UCB-V can exhibit instability in arm-pulling rates but achieves refined regret bounds.
A new algorithm learns optimal source placement in large networks.
problem Optimizing source placement in large scale networks with unknown processes.
method Graph-Kernel Multi-Armed Bandit (Grab-UCB) algorithm with adaptive graph dictionary model.
result Online learning algorithm outperforms offline methods in terms of cumulative regret, sample efficiency, and computational complexity.
A classic setting of the stochastic K-armed bandit problem is considered in this note. In this problem it has been known that KL-UCB policy achieves the asymptotically optimal regret bound and KL-UCB+ policy empirically performs better than the KL-UCB policy although the regret bound for the original form of the KL-UCB…
The multi-armed bandit problem has been extensively studied under the stationary assumption. However in reality, this assumption often does not hold because the distributions of rewards themselves may change over time. In this paper, we propose a change-detection (CD) based framework for multi-armed bandit problems und…
Active learning suffers from biased non-response, which this paper addresses.
problem Active learning's effectiveness is compromised by biased non-response in real-world contexts.
method Proposes a cost-based correction to the sampling strategy, UCB-EU, to mitigate the impact of biased non-response.
result UCB-EU successfully reduces the harm from labelling non-response in many settings.
UCB algorithm adapted for large-scale, non-sub-Gaussian problems.
problem Selecting the best alternative from a large set of options with non-sub-Gaussian performance distributions.
method Adapted UCB algorithm for non-sub-Gaussian settings, focusing on sample size and meta-UCB selection.
result UCB algorithms can achieve sample optimality in large-scale, non-sub-Gaussian problems.
We consider -armed stochastic bandits and consider cumulative regret bounds up to time . We are interested in strategies achieving simultaneously a distribution-free regret bound of optimal order and a distribution-dependent regret that is asymptotically optimal, that is, matching the lower b…
Improved UCB method for stochastic bandits using distance tuning.
problem Improving performance in stochastic bandit problems.
method Tuning confidence bounds based on bandit distance.
result Empirically shows increased performance compared to existing methods.
New algorithms improve on bandit feedback in matrix games with unknown payoff matrices.
problem Improving performance in matrix games with unknown payoff matrices and bandit feedback.
method Regret analyses of variants of UCB and K-learning.
result New algorithms achieve lower regret compared to adversarial bandit algorithms.
We consider the sequential Bayesian optimization problem with bandit feedback, adopting a formulation that allows for the reward function to vary with time. We model the reward function using a Gaussian process whose evolution obeys a simple Markov model. We introduce two natural extensions of the classical Gaussian pr…
Fine-grained gap-dependent regret bounds for reinforcement learning.
problem Achieving optimal regret bounds for reinforcement learning with suboptimality gaps.
method Developed novel analytical frameworks and refined algorithms for UCB-based and non-UCB-based reinforcement learning.
result Established the first fine-grained gap-dependent regret bounds for both UCB-based and non-UCB-based algorithms.
A new UCB algorithm for heavy-tailed bandits with near-optimal regret.
problem Sequential decision making in uncertain environments with heavy-tailed rewards.
method Data-driven, distribution-free UCB algorithm combining resampled median-of-means and UCB.
result Near-optimal regret bound for heavy-tailed distributions.
This paper improves GP-UCB by using a shifted exponential distribution for confidence parameters.
problem Theoretical confidence parameter in GP-UCB increases with iterations, leading to large values.
method Introduced IRGP-UCB, a randomized variant of GP-UCB using a shifted exponential distribution for confidence parameters.
result IRGP-UCB achieves sub-linear regret without increasing the confidence parameter.
BaNk-UCB tackles batched nonparametric bandits with k-NN regression and UCB.
problem Sequential decision-making with limited online feedback in domains like medicine and marketing.
method Combines k-NN regression with UCB principle for fully nonparametric, adaptive, and simple implementation.
result Near-optimal regret guarantees under Lipschitz smoothness and margin assumptions, with minimax-optimal rates.
GP-UCB performs suboptimally under certain conditions, as shown by a new regret lower bound.
problem The suboptimality of GP-UCB under polynomial effective optimism.
method Analysis of effective optimism level and new regret lower bound.
result GP-UCB is not minimax optimal under polynomial growth of effective optimism.
In this paper we propose and explore the k-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates. We focus on a setting where the covariates are supported on a metric space of low intrinsic dimension, such as a manifold embedded within a high dimensional ambient feature space. The algorithm is concept…
New algorithm minimizes regret in multi-agent bandit problem with probabilistic communication.
problem Minimizing group regret in multi-agent multi-armed bandit problem with probabilistic communication.
method Proposes a new UCB-based algorithm for decentralized multi-agent multi-armed bandit problem on -regular graphs with probabilistic communication.
result The proposed algorithm outperforms state-of-the-art algorithms in minimizing group regret.
A new method optimizes robustness measures under input uncertainty using randomized Gaussian process upper confidence bound.
problem Optimizing robustness measures under input uncertainty.
method Randomized robustness measure GP-UCB (RRGP-UCB) that samples β from a chi-squared-based distribution.
result RRGP-UCB provides tight bounds on expected regret.
UCB exploration improves best arm identification in fixed-budget settings.
problem Best arm identification in fixed-budget scenarios.
method Adaptive allocations based on upper confidence bounds (UCBs) with prior information learning.
result Empirically and theoretically efficient for Bayesian BAI problem with improved performance.
UCB-RS uses RS to improve UCB for online advertising.
problem Improving recommendation in online advertising.
method UCB-RS, combining UCB with recommendation system.
result UCB-RS outperforms other reinforcement learning methods in RecoGym.
TS-UCB improves Thompson Sampling with minimal extra computation.
problem Online decision problems with bandit feedback.
method TS-UCB uses posterior samples and upper confidence bounds to select arms.
result TS-UCB achieves lower regret on various datasets.
UCB algorithm's arm-sampling behavior is revealed, leading to new insights and proofs.
problem Optimizing multi-armed bandit algorithms for worst-case scenarios.
method Analysis of UCB algorithm's arm-sampling behavior and process-level characterization.
result UCB's arm-sampling rates are asymptotically deterministic, regardless of problem complexity.
New method uses offline data to improve online bandit learning, even when distributions differ.
problem Improving online bandit learning with different offline and online distributions.
method MIN-UCB policy that adapts to offline data when informative, achieving tight regret bounds.
result MIN-UCB policy outperforms UCB policy with offline data and provides tight regret bounds.
New approach incentivizes strategic agents to explore, making exploration almost free.
problem Incentivized exploration in multi-armed bandits with long-term strategic agents.
method Simple incentive-provision strategy, best arm identification algorithm, and UCB lower bound.
result Exploration can be (almost) free when there are many learning agents.
FP-UCB algorithm achieves bounded regret for finitely parameterized multi-armed bandits.
problem Finitely parameterized multi-armed bandits with unknown but known parameter set.
method FP-UCB algorithm using structural information about the parameter set.
result FP-UCB achieves bounded regret under structural condition, logarithmic otherwise.
GP-UCB resolves sublinear regret for kernelized bandits.
problem Minimizing regret in kernelized bandit problems.
method Using a new regularization technique for kernel ridge estimators, improving GP-UCB's sublinear regret rate.
result GP-UCB achieves nearly optimal sublinear regret for the Matérn kernel.
Unified theory for UCB policies in total and max bandit problems.
problem Order optimality of UCB policies in max bandit problems.
method Unified definition of UCB policy using oracle quantity and failure count.
result UCB policies are order optimal in both total and max bandit problems.
Paper compares UCB policy to new adaptive RL methods.
problem Optimal adaptive policies for Markovian decision processes with unknown transition probabilities.
method Compared UCB policy with MDP-Deterministic Minimum Empirical Divergence and Posterior sampling methods.
result MDP-DMED outperforms UCB in the tested RL scenarios.
New UCB algorithm for learning PSRs with tractable computation and accuracy.
problem Learning predictive state representations in sequential decision-making problems.
method Proposes a novel UCB-type algorithm with a bonus term to estimate PSRs accurately and efficiently.
result First known UCB-type approach for PSRs with guaranteed model accuracy and computational tractability.