A new algorithm solves a regional multi-armed bandit problem with group information.
problem Optimizing decisions with unknown parameters across groups.
method UCB-g algorithm combining UCB and greedy principles.
result Proves the order-optimality of UCB-g and establishes a matching lower bound.
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 RL algorithm optimizes policies with bandit feedback, matching previous bounds.
problem Optimizing policies with unknown transitions and bandit feedback.
method Optimistic Trust Region Policy Optimization (TRPO) algorithm.
result Sub-linear regret bounds for both stochastic and adversarial rewards.
In data-limited settings, stochastic policies can outperform deterministic ones in bandit problems.
problem Making reliable decisions with limited data in bandit problems.
method Designing TRUST, an algorithm that uses localization laws and relative pessimism.
result TRUST achieves comparable sample complexity to LCB on minimax problems but is significantly lower on few-sample problems.
Proposes a new Hawkes process bandit model for disaster search and rescue.
problem Forecasting and detecting spatio-temporal events with undersampled or biased data.
method Upper confidence bound algorithm using Bayesian spatial Hawkes process estimation.
result Model outperforms state-of-the-art spatial MAB algorithms in disaster search and rescue.
This paper studies adversarial attacks on Gaussian process bandits.
problem Adversarial attacks on Gaussian process bandits to manipulate optimal function regions.
method Proposes various adversarial attack methods on GP bandits, including white-box and black-box attacks.
result Adversarial attacks can force GP bandits to optima in target regions even with low attack budgets.
Algorithm improves wildlife protection patrols.
problem Balancing exploration and exploitation in patrolling vast protected areas.
method Formulated as a stochastic multi-armed bandit problem, leveraging smoothness and decomposability.
result Algorithm LIZARD improves performance on real-world poaching data.
Smooth Contextual Bandits bridge two previously studied extremes of non-differentiable and parametric-response bandits.
problem Nonparametric contextual bandits with Hölder smoothness.
method Developed a novel algorithm that optimally balances between non-differentiable and parametric-response bandits.
result Proved the algorithm achieves rate-optimal regret for all smoothness settings.
The paper tackles restless bandits with limited observation, proposing a method to analyze and approximate their optimal strategies.
problem Restless bandits with limited observation.
method General probabilistic model, PCL analysis, and approximation process.
result The proposed method can transform the problem into a finite-state problem, enabling the use of existing algorithms.
Kernelized bandit algorithm tackles adaptive contextual bandits with single-index models.
problem Adaptive contextual bandits with single-index models and unknown link functions.
method Kernelized ε-greedy algorithm combining Stein-based index estimation and kernel ridge regression for reward functions.
result Unified framework for simultaneous learning and inference in single-index contextual bandits.
A new algorithm optimizes local objectives in federated learning with heterogeneous clients.
problem Optimizing local objectives in federated learning with heterogeneous client data.
method Proposes PF-PNE algorithm with double elimination strategy.
result PF-PNE algorithm optimizes local objectives with arbitrary heterogeneity and protects client data confidentiality.
In many scientific and engineering applications, we are tasked with the maximisation of an expensive to evaluate black box function f f f . Traditional settings for this problem assume just the availability of this single function. However, in many cases, cheap approximations to f f f may be obtainable. For example, the exp…
New algorithm for adaptive experimental design in scientific settings.
problem Identifying true positives while controlling false discoveries in adaptive experimental design.
method Provably sample efficient adaptive algorithm for FDR control.
result First provably sample efficient adaptive algorithm for adaptive experimental design.
New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
Algorithm tackles adaptive discretization in adversarial Lipschitz bandits for dynamic pricing and auctions.
problem Adaptive discretization in adversarial Lipschitz bandits.
method Adversarial Zooming algorithm for adaptive discretization.
result First algorithm for adversarial Lipschitz bandits with instance-dependent regret bounds.
New algorithm catches moving subspaces in bandit problems.
problem Adapt to changing low-dimensional latent subspaces in bandit settings.
method Piecewise-stationary low-rank linear contextual bandits with CUSUM-style boundary detection.
result Achieves intrinsic rank dynamic regret rate of O ( r T ) O(r\sqrt{T}) O ( r T ) . Autonomous systems can be used to search for sparse signals in a large space; e.g., aerial robots can be deployed to localize threats, detect gas leaks, or respond to distress calls. Intuitively, search algorithms may increase efficiency by collecting aggregate measurements summarizing large contiguous regions. However…
Paper presents a new method for optimizing hyperparameters in machine learning models.
problem Optimizing hyperparameters in machine learning models, especially for black-box functions.
method Adaptive local Bayesian optimization over multiple discrete variables, combining region reliability, Gaussian process kernel, and MAB approach.
result Method outperforms baseline algorithms by up to +20.39% across different tasks.
A new algorithm tackles delayed combinatorial semi-bandit with causal relations.
problem Optimizing decisions in a non-stationary environment with delayed and causally related rewards.
method Formalized as a non-stationary delayed combinatorial semi-bandit problem, the approach models causal relations with a directed graph in a stationary structural equation model. The agent learns these relations from delayed feedback to optimize decisions.
result Proved a regret bound for the proposed algorithm's performance.
AUCRSS detects change points in partially observed multivariate autocorrelated data.
problem Detecting change points in multivariate autocorrelated data with limited sensing resources.
method Adaptive Upper Confidence Region (AUCRSS) with state space model (SSM), adaptive sampling policy, and generalized likelihood ratio test.
result The method outperforms existing approaches in detecting change points efficiently.
This paper explores policy improvement using various f-divergences, enhancing stability in reinforcement learning.
problem Ensuring stability in reinforcement learning algorithms through policy improvement with trust regions.
method The paper considers a general class of f-divergences and derives policy update rules, including the KL divergence as a special case.
result The study reveals different policy updates and evaluations for various f-divergences, including Pearson χ 2 χ^2 χ 2 -divergence and KL divergence. Improved batch-size independent regret bounds for nonlinear reward functions.
problem Nonlinear reward functions in combinatorial multi-armed bandit problems.
method Introducing Gini-weighted smoothness to account for both nonlinearity and concentration properties of arms.
result Achieved dramatic improvements in upper bounds for the probabilistic maximum coverage problem.
ZoomRL learns efficient strategies for large state-action spaces using a metric.
problem Handling large state-action spaces in reinforcement learning.
method ZoomRL leverages continuous bandits to adaptively discretize the joint space.
result Achieves worst-case regret of $ ilde{O}(H^{ rac{5}{2}} K^{ rac{d+1}{d+2}})$ .
New method minimizes experiment cost while maintaining accuracy.
problem Minimizing cost in experiments with interference or other concerns.
method Synthetically Controlled Thompson Sampling (SCTS).
result Minimizes regret and maintains inferential ability.
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
Unified formulation bridges adversarial and nonstationary bandits.
problem Handling time-varying reward distributions in multi-armed bandit problems.
method Unified oracle that switches between adversarial and nonstationary bandit oracles based on window size.
result Optimal regret achieved with matching lower bound.
Paper studies attacks on bandit algorithms and shows how attackers can manipulate data to hijack behavior.
problem Potential attacks on bandit algorithms can cause catastrophic loss in real-world applications.
method Proposes a framework of offline and online attacks on bandit algorithms using convex optimization and adaptive strategies.
result Attackers can force bandit algorithms to pull target arms with high probability by manipulating data.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
Algorithm identifies best arm in linked bandits with reduced feedback.
problem Best arm identification in linked bandits with reduced feedback.
method Combines uniform sampling with regular bandit algorithm.
result Almost matching upper and lower bounds on sample complexity.
Graph-Triggered Bandits unify rested and restless bandits with graph-defined arm interactions.
problem Modeling sequential decision-making problems with evolving arm rewards.
method Graph-Triggered Bandits (GTBs) framework that generalizes rested and restless bandits using a graph.
result Rested and restless bandits are special cases of GTBs for suitable graphs.
New definition resolves ambiguity in non-stationary bandit classification.
problem Ambiguity in classifying non-stationary bandits using existing definitions.
method Introducing a formal definition that resolves ambiguity and provides a unified approach.
result Unified approach applicable to both Bayesian and frequentist formulations, resolves classification issues.
Unified approach for non-stationary and clustered bandits.
problem Solving non-stationary and clustered bandits with overlapping solutions.
method Test of homogeneity for seamless integration of non-stationary and clustered bandits.
result Unified solution framework for change detection and cluster identification.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
New algorithm learns optimal exploration parameters for contextual bandits.
problem Learning optimal exploration in contextual bandits.
method Proposes two algorithms that learn optimal exploration parameters online based on context and reward.
result Demonstrates improved performance in learning optimal exploration compared to traditional methods.
A new method for dueling bandits improves performance.
problem Improving decision-making in dueling bandits.
method Sup-KLUCB method for K-armed dueling bandits, converting Copeland dueling bandits into standard MAB problems.
result Sup-KLUCB outperforms state-of-the-art methods in Copeland dueling bandits.
Study on indexability of restless multi-armed bandits and rollout policy performance.
problem Maximizing discounted rewards in finite state restless multi-armed bandit problems.
method Decouple the problem into single-armed restless bandits, analyze using value iteration, and compare with Whittle index policy.
result Demonstrates conditions for indexability and compares performance of index policy and rollout policy.
Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.
New insights into multi-armed bandits with budget constraints.
problem Multi-armed bandits with supply/budget constraints.
method Characterization of logarithmic regret rates, simple regret, and reduction to other bandit problems.
result Full characterization of logarithmic, instance-dependent regret rates for BwK.
Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the ε ε ε -Thresholding Bandit Problem (TBP). result Asymptotically optimal algorithm for TBP.
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.
New method for contextual bandits with corrupted context.
problem Contextual bandits with corrupted context in online settings.
method Combining contextual bandit and multi-armed bandit approaches.
result Improved learning from all iterations, including corrupted ones.
A new algorithm for top-k combinatorial bandits with full-bandit feedback.
problem Optimizing decisions among subsets of arms with only aggregate rewards observed.
method CSAR algorithm using Hadamard matrices for estimating individual arm rewards.
result Proved a tight lower bound on sample complexity for k = O ( 1 ) k=O(1) k = O ( 1 ) . A new framework for structured bandits using influence diagrams and variational Thompson sampling.
problem Complex statistical dependencies in structured bandit problems.
method Influence diagram framework, variational Thompson sampling, tracking structured posterior distribution.
result Empirically evaluated algorithms perform as well as or better than existing baselines.
Factored bandits model learns with limited feedback using decomposable actions.
problem Limited feedback learning with decomposable actions.
method Introduces factored bandits model, provides anytime algorithm, and matching upper and lower bounds.
result Improves regret bounds for utility-based dueling bandits.
New algorithm for nonstationary multi-armed bandits with optimal performance.
problem Nonstationary multi-armed bandits with changing model parameters over time.
method Adaptive Resetting Bandit (ADR-bandit) algorithm using adaptive windowing techniques.
result ADR-bandit achieves nearly optimal performance in both abrupt and gradual changes.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.