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…
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,742 papers · 148 categories
Trend · papers per month
48 results for “UCB policy”
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.
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…
A new UCB policy improves reward-cost ratio estimation in budgeted MAB.
problem Maximizing reward-cost ratio under budget constraints.
method ω-UCB policy with asymmetric confidence intervals.
result Logarithmic regret and superior performance in various settings.
In this paper we consider the basic version of Reinforcement Learning (RL) that involves computing optimal data driven (adaptive) policies for Markovian decision process with unknown transition probabilities. We provide a brief survey of the state of the art of the area and we compare the performance of the classic UCB…
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.
This paper is about index policies for minimizing (frequentist) regret in a stochastic multi-armed bandit model, inspired by a Bayesian view on the problem. Our main contribution is to prove that the Bayes-UCB algorithm, which relies on quantiles of posterior distributions, is asymptotically optimal when the reward dis…
Optimal policy for multi-armed multi-action bandits with unknown parameters.
problem Optimal sequential action selection for multi-armed multi-action bandits with unknown parameters.
method Occupancy-Measured-Reward Index Policy (OMRIP) and R(MA)^2B-UCB algorithm.
result Asymptotically optimal policy with sub-linear regret and low computational complexity.
The paper analyzes the sliding regret of stochastic bandit algorithms.
problem Measuring the one-shot behavior of no-regret algorithms in stochastic bandits.
method Introducing sliding regret to measure the worst pseudo-regret over a time-window.
result Randomized methods have optimal sliding regret, while index policies have the worst possible sliding regret.
This paper improves Q-learning bounds using reference-advantage decomposition.
problem Improving Q-learning bounds in MDPs with positive suboptimality gaps.
method Develops a novel error decomposition framework to prove gap-dependent regret bounds.
result Establishes logarithmic gap-dependent regret bounds for Q-learning.
Contrastive UCB improves RL by learning feature representations efficiently.
problem Improving feature learning in RL for online decision making.
method Proposes UCB-based contrastive learning algorithms for RL in MDPs and MGs.
result Proves sample efficiency in learning optimal policies and Nash equilibria.
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.
EgalMAB solves fair resource allocation in stochastic bandits.
problem Fair resource allocation in a stochastic multi-armed bandit setting.
method Design and analysis of UCB-based policy EgalUCB.
result Established upper bounds on cumulative regret.
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.
A decentralized policy achieves logarithmic regret for multi-agent MAB problems with communication constraints.
problem Decentralized policy for multi-agent MAB problems with option availability and communication constraints.
method Upper Confidence Bound (UCB) algorithms with non-stationary stochastic communication protocol.
result Guaranteed logarithmic regret for non-fully connected spatial graphs with communication constraints.
Efficient RL algorithms for linear function approximation with limited adaptivity constraints.
problem Limited adaptivity in reinforcement learning with linear function approximation.
method Proposed two efficient online RL algorithms for episodic linear Markov decision processes under batch learning and rare policy switch models.
result Achieved efficient regret bounds for both batch learning and rare policy switch models, with substantial reduction in adaptivity.
AR design reduces multi-armed bandit experiment cost.
problem Comparing multi-armed bandit algorithms requires many restarts.
method Artificial Replay (AR) design for bandit experiments.
result AR reduces experimental cost by requiring only user interactions.
Develops algorithms for CCBs with non-linear costs, improving safety and performance.
problem Safety constraints in sequential decision making with non-linear arm costs.
method Innovative algorithms using Inverse Gap Weighting (IGW) and online regression oracle.
result Sub-linear regret bounds for C-SquareCB and first-order regret for C-FastCB.
Proposes a method to avoid excessive exploration in reinforcement learning.
problem Avoiding excessive exploration in reinforcement learning to deploy it in practice.
method Designs a novel algorithm using UCB reinforcement learning policy with adaptive exploration constraints.
result Proves that the approach remains conservative while minimizing regret in tabular settings and validates on real-world tasks.
A new method optimizes material discovery by balancing exploration and exploitation.
problem Substantial experimental costs and lengthy development periods in material discovery.
method Threshold-Driven UCB-EI Bayesian Optimization (TDUE-BO) method.
result TDUE-BO significantly outperforms traditional BO methods in material discovery.
Sequential decision making for lifetime maximization is a critical problem in many real-world applications, such as medical treatment and portfolio selection. In these applications, a "reneging" phenomenon, where participants may disengage from future interactions after observing an unsatisfiable outcome, is rather pre…
A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with…
New algorithm reduces RL complexity with low switching costs.
problem Exploration-exploitation dilemma in RL with complex models.
method Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation.
result Achieves minimax optimal regret of and near-optimal policy switching cost.
SPAQL improves RL by adaptively partitioning state-action space and learning a time-invariant policy.
problem Efficient model-free reinforcement learning with scalable algorithms.
method Adaptive Q-learning with UCB and Boltzmann exploration, automatically tuning temperature.
result SPAQL converges faster and uses fewer resources than AQL, showing higher sample efficiency.
This paper proposes a novel policy for a group of agents to, individually as well as collectively, solve a multi armed bandit (MAB) problem. The policy relies solely on the information that an agent has obtained through sampling of the options on its own and through communication with neighbors. The option selection po…
Algorithm improves continuous control with context, achieving provable efficiency.
problem Building an agent that generalizes to unseen environments in continuous control.
method Uses upper confidence bound (UCB) to refine decoder estimates and balance exploration-exploitation.
result Proves $\widetilde{O}\left(\sqrt{T}
ight)$ regret bound and -suboptimal policy transfer.
Algorithm reduces decision-making errors in multi-agent bandit problems.
problem Minimizing decision errors in multi-agent multi-armed bandit problems.
method RBO-Coop-UCB algorithm with Bayesian change point detection.
result Expected group regret is upper bounded by .
This research develops an efficient reinforcement learning method for undercomplete POMDPs.
problem Learning undercomplete Partially Observable Markov Decision Processes (POMDPs) is computationally hard.
method OOM-UCB algorithm for episodic finite undercomplete POMDPs.
result Achieves optimal sample complexity of for finding an -optimal policy.
Optimized Sharpe Ratio for better risk-adjusted decision-making in multi-armed bandits.
problem Challenging to optimize Sharpe Ratio (SR) in multi-armed bandits (MAB) due to constant regret.
method Proposed UCB-RSSR algorithm for RSSR maximization, derived path-dependent concentration bound and regret guarantees.
result UCB-RSSR outperforms existing algorithms and finds applications in risk-aware portfolio management.
This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistence, and e…
Paper tackles transfer RL under unobserved context, developing methods to reduce bias.
problem Transfer RL with unobserved contextual information leading to biased models.
method Develops causal bounds on transition and reward functions using demonstrator's data.
result Proposes Q learning and UCB-Q learning algorithms that converge to true value function without bias.
New algorithms use neural networks to minimize regret in contextual bandits.
problem Minimizing regret in sequential decisions with side information.
method Proposes NN-UCB and NTK-UCB algorithms using neural networks.
result Proves sublinear regret bounds for contextual bandits.
Improved gap-dependent bounds for reinforcement learning with linear approximations.
problem Achieving nearly minimax-optimal performance with linear function approximation.
method Developed and analyzed the LSVI-UCB++ algorithm and its concurrent variant.
result First gap-dependent regret bound for nearly minimax-optimal algorithm LSVI-UCB++.
Fast Calculation of the Knowledge Gradient for Optimization of Deterministic Engineering Simulationscs.CE
A novel efficient method for computing the Knowledge-Gradient policy for Continuous Parameters (KGCP) for deterministic optimization is derived. The differences with Expected Improvement (EI), a popular choice for Bayesian optimization of deterministic engineering simulations, are explored. Both policies and the Upper …
Optimizes resource allocation for distributed parameter estimation in sensor networks.
problem Maximizing accuracy in parameter estimation with limited resources.
method Formulates a data collection and collaboration policy design problem as a Fisher information maximization problem. Proposes multi-armed bandit algorithms for learning the optimal policy.
result Identifies optimal data collection and collaboration policies that balance resource use and estimation accuracy.
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.
New bandit model accounts for user departures in recommender systems.
problem Capturing user departures in recommender systems with multi-armed bandits.
method Proposes a novel multi-armed bandit setup with two types of users and analyzes optimal and efficient algorithms.
result Achieves optimal and efficient learning algorithms for user types and reward probabilities.
Motivated by recommendation problems in music streaming platforms, we propose a nonstationary stochastic bandit model in which the expected reward of an arm depends on the number of rounds that have passed since the arm was last pulled. After proving that finding an optimal policy is NP-hard even when all model paramet…
In this paper, we propose a cost-aware cascading bandits model, a new variant of multi-armed ban- dits with cascading feedback, by considering the random cost of pulling arms. In each step, the learning agent chooses an ordered list of items and examines them sequentially, until certain stopping condition is satisfied.…
New MAB model incentivizes user arm-pulling with self-reinforcing preferences.
problem Balancing exploration and exploitation in recommender systems with incentivized user preferences.
method Proposes a new MAB model with random arm selection and two policies: At-Least- Explore-Then-Commit and UCB-List.
result Achieves expected regret and expected payment over a time horizon .
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.
New algorithm for traffic routing in congested conditions.
problem Optimal routing in congested traffic networks.
method Congested Bandits model, UCB algorithm, iterative least squares planner.
result No-regret algorithms for congestion-aware routing.
A new bandit algorithm observes arm rewards before playing, reducing regret.
problem Balancing exploration and exploitation with pre-observation costs.
method Design of OBP-UCB for single-player and C-MP-OBP for multi-player settings.
result Proved regret bounds for both single-player and multi-player settings.
Uplifting Banditsstat.ML
UCB algorithms estimate uplifts in multi-variable reward systems.
problem Marketing campaigns and recommender systems with multiple outcome variables.
method UCB-style algorithms for estimating uplifts over a baseline.
result Sublinear regret bounds for multiple problem variants.
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.
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.
We study the stochastic multi-armed bandit (MAB) problem in the presence of side-observations across actions that occur as a result of an underlying network structure. In our model, a bipartite graph captures the relationship between actions and a common set of unknowns such that choosing an action reveals observations…
BONSAI optimizes parameters while respecting a default configuration, reducing unnecessary changes.
problem Standard BO pushes weakly relevant parameters to the boundary, making it hard to distinguish between important and spurious changes.
method BONSAI is a default-aware BO policy that prunes low-impact deviations from a default configuration while controlling acquisition value loss.
result BONSAI matches the GP-UCB regret rate while recovering the minimal- solution, reducing the number of non-default parameters in recommended configurations.