SCaLE tackles dynamic regret in noisy bandit feedback with switching costs.
problem Unbounded metric movement costs in bandit online convex optimization.
method SCaLE algorithm for high-dimensional dynamic quadratic hitting costs and ℓ 2 \ell_2 ℓ 2 -norm switching costs, with spectral regret analysis. result First algorithm achieving sub-linear dynamic regret without hitting cost knowledge.
New method reduces linear regret in high-dimensional bandit problems.
problem Heavy spectral tails in streaming matrices lead to linear regret in sketch-based linear bandits.
method Dyadic Block Sketching, a multi-scale matrix sketching approach.
result Achieves sublinear regret bounds without prior knowledge of streaming matrix properties.
Study of bandit problem with Poisson decision times and Lévy processes.
problem Continuous-time multi-armed bandit problem with Poisson decision times.
method Gittins index policy applied to spectrally one-sided Lévy processes.
result Gittins index converges to classical Lévy bandit index.
Lower bounds on eigenspectrum show rich action spaces force polynomial regret in linear bandits.
problem Understanding the minimum eigenvalue growth in linear bandits with rich action sets.
method Non-asymptotic lower bound on eigenspectrum of design matrix.
result Minimum eigenvalue of expected design matrix grows as Ω ( n ) Ω(\sqrt{n}) Ω ( n ) for sub-linear regret. Unified analysis of kernel-based and locally adaptive bandit optimization methods.
problem Performance of bandit optimization algorithms in RKHS functions.
method Investigates the relationship between kernel regularity and algorithmic performance, characterizing spectral properties of various kernels.
result Unified framework for analyzing kernel-based and locally adaptive bandit algorithms, deriving explicit regret bounds.
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.
Paper tackles efficient BAI in graph-smooth bandits.
problem Best arm identification with graph smoothness constraint.
method Gradient ascent algorithm for sample complexity.
result Asymptotically optimal strategy for BAI.
Improved guarantees for misspecified kernelized bandit optimization.
problem Misspecification in kernelized bandit optimization.
method Localization and domain splitting techniques.
result Logarithmic or polylogarithmic growth of misspecification amplification.
New algorithms reduce dueling bandits' regret with neural networks and efficient exploration.
problem Optimizing dueling bandits with neural networks for better performance.
method Combines shallow exploration strategies with neural networks for utility approximation, using iterative self-improvement and spectral analysis to reduce network width.
result Achieves sublinear regret of O ~ ( d ∑ t = 1 T σ t 2 + d T ) \widetilde{\mathcal{O}}(d\sqrt{\sum_{t=1}^{T} σ_t^2} + \sqrt{dT}) O ( d ∑ t = 1 T σ t 2 + d T ) . Study bandit problem on smooth graph functions for recommender systems.
problem Online learning problems involving graphs, like content-based recommendation.
method Introduced spectral bandit problem and two algorithms that scale linearly in effective dimension.
result Learned user preferences for thousands of items from just tens nodes evaluations.
This paper analyzes the multi-armed bandit problem using frequency-domain methods.
problem The exploration-exploitation trade-off in sequential decision-making.
method Proposes a frequency-domain analysis framework, reformulating the bandit process as a signal processing problem.
result Confidence bound term in UCB algorithm is equivalent to a time-varying gain in frequency domain.
The paper tackles a bandit problem on graphs with smooth functions, aiming to recommend items with high expected ratings.
problem Online learning problems involving graphs, such as content-based recommendation.
method Introduced the notion of effective dimension and proposed two algorithms for solving the problem.
result The algorithms can learn good estimators of user preferences from just tens of nodes evaluations.
Efficient algorithms for low-rank bandits using subspace recovery.
problem Contextual bandits with low-rank reward matrices.
method Spectral methods for subspace recovery, reformulating as linear bandits.
result Nearly optimal policy evaluation and best policy identification, minimax guarantees for regret minimization.
A new algorithm reduces the time and space complexity for multinomial logistic bandits.
problem High-dimensional feedback in multinomial logistic bandits makes existing algorithms inefficient.
method Integrates frequent directions matrix sketching into OFUL-MLogB to reduce time and space complexity.
result Achieves a regret bound of i l d e O ( Δ T ( K d ln Δ T + m ) T ) ilde{\mathcal{O}}(Δ_T(Kd\lnΔ_T+m)\sqrt{T}) i l d e O ( Δ T ( K d ln Δ T + m ) T ) . New spectral methods improve matrix estimation in RL with low-rank structure.
problem Estimating matrices with low-rank structure in reinforcement learning.
method Spectral-based matrix estimation approaches.
result Spectral methods efficiently recover singular subspaces and minimize entry-wise error.
New approach speeds up DNA sequence alignment.
problem Efficiently estimating alignment scores for large sets of reads.
method Rank-one crowdsourcing models and multi-armed bandit algorithm.
result Adaptive algorithm identifies pairs with large alignment scores.
New algorithms for private generalized linear contextual bandits.
problem Private estimation and optimization for generalized linear models under differential privacy.
method Developed algorithms for stochastic and adversarial contexts under shuffle and joint differential privacy.
result Achieved private regret bounds for generalized linear models, differing from non-private rates by factors of d / ε \sqrt{d/\varepsilon} d / ε and d / ε \sqrt{d/\varepsilon} d / ε respectively. This paper explores the complexity of learning representations in contextual linear bandits.
problem Understanding the complexity of representation learning in contextual linear bandits.
method Systematic approach to representation learning in contextual linear bandits, focusing on instance-dependent perspective.
result Representation learning is fundamentally more complex than linear bandits, with some cases being arbitrarily harder.
Bandit problem on graphs aims to recommend items with high expected ratings.
problem Online learning problems involving graphs, such as content-based recommendation.
method Study of a bandit problem on graphs, introducing effective dimension and proposing algorithms.
result Proposed algorithms scale linearly and sublinearly in the effective dimension, improving cumulative regret.
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 decentralized algorithm minimizes cumulative regret in stochastic linear bandits with safety constraints.
problem Efficiently solving a linear bandit-optimization problem over a network of agents with safety constraints.
method DLUCB: a fully decentralized algorithm that minimizes cumulative regret through UCB strategy and consensus procedure.
result Near-optimal regret performance of O ( d log N T N T ) \mathcal{O}(d\log{NT}\sqrt{NT}) O ( d log N T N T ) with O ( d N 2 ) \mathcal{O}(dN^2) O ( d N 2 ) communication rate. SpectralTS improves efficiency of Thompson Sampling for graph-based bandits.
problem Efficiently solving bandit problems with smooth payoffs on graphs.
method SpectralTS algorithm for a graph-based bandit problem with effective dimension d.
result SpectralTS offers a computationally more efficient alternative with regret scaling as d*sqrt(T ln N).
We study a multi-armed bandit problem where the rewards exhibit regime switching. Specifically, the distributions of the random rewards generated from all arms are modulated by a common underlying state modeled as a finite-state Markov chain. The agent does not observe the underlying state and has to learn the transiti…
Improved Bandit PCA with optimal regret bound.
problem Minimizing regret in online PCA with bandit feedback.
method Combines online mirror descent and multiscale exploration.
result Minimax optimal regret bound of r d T r\sqrt{dT} r d T . New algorithms robust to adversarial data achieve optimal performance.
problem Adversarial robustness in high-dimensional online learning problems.
method Alternating minimization scheme combining least-squares and convex reweighting.
result Achieves optimal robustness guarantees without distributional assumptions.
We propose a new algorithm for hyperparameter selection in machine learning algorithms. The algorithm is a novel modification of Harmonica, a spectral hyperparameter selection approach using sparse recovery methods. In particular, we show that a special encoding of hyperparameter space enables a natural group-sparse re…
We study a decentralized cooperative stochastic multi-armed bandit problem with K K K arms on a network of N N N agents. In our model, the reward distribution of each arm is the same for each agent and rewards are drawn independently across agents and time steps. In each round, each agent chooses an arm to play and subsequ…
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 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.
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 ) . 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.
Stochastic multi-armed bandits form a class of online learning problems that have important applications in online recommendation systems, adaptive medical treatment, and many others. Even though potential attacks against these learning algorithms may hijack their behavior, causing catastrophic loss in real-world appli…
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.
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.
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 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.
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.
A novel beam training scheme optimizes multi-hop THz communications with up to 75% performance gain.
problem Optimizing beam training for multi-hop THz communications with high data rates and low time overhead.
method Developed a reinforcement learning-based hierarchical beam training scheme with dynamic training levels.
result The proposed scheme achieves up to 75% performance gain in spectral efficiency compared to conventional methods.
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.
Survey and compare PAC-Bayes bounds for bandit problems.
problem Designing and evaluating bandit algorithms with strong performance guarantees.
method PAC-Bayes bounds applied to bandit problems.
result PAC-Bayes bounds useful for offline bandit algorithms, but loose for online algorithms.