High-Probability Regret Bounds for Bandit Online Linear Optimization

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  2008-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Advances in Neural Information Processing Systems 20 (NIPS 2007)

  2008cited by this paper
• Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization

  2008cited by this paper
• Stochastic Linear Optimization under Bandit Feedback

  2008cited by this paper
• The On-Line Shortest Path Problem Under Partial Monitoring

  2007cited by this paper
• The Price of Bandit Information for Online Optimization

  2007cited by this paper
• IEEE TRANSACTIONS ON INFORMATION THEORY , VOL . ? , NO . ? , ? 200 ? 1 Improved Risk Tail Bounds for On-Line Algorithms

  2007cited by this paper
• Robbing the bandit: less regret in online geometric optimization against an adaptive adversary

  2006cited by this paper
• Prediction, learning, and games

  2006cited by this paper
• Efficient algorithms for online decision problems

  2005cited by this paper
• Provably competitive adaptive routing

  2005cited by this paper
• Online decision problems with large strategy sets

  2005cited by this paper
• Adaptive routing with end-to-end feedback: distributed learning and geometric approaches

  2004cited by this paper
• Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary

  2004cited by this paper
• The Nonstochastic Multiarmed Bandit Problem

  2002cited by this paper
• Path Kernels and Multiplicative Updates

  2002cited by this paper
• On Tail Probabilities for Martingales

  1975cited by this paper

• Efficient Swap Regret Minimization in Combinatorial Bandits

  2026cites this paper
• Online Budget Allocation with Censored Semi-Bandit Feedback

  2025cites this paper
• Efficient Kernelized Learning in Polyhedral Games Beyond Full-Information: From Colonel Blotto to Congestion Games

  2025influential citation
• Contextual Online Pricing with (Biased) Offline Data

  2025cites this paper
• Towards Fundamental Limits for Active Multi-distribution Learning

  2025cites this paper
• Adversarial bandit optimization for approximately linear functions

  2025cites this paper
• Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries

  2025cites this paper
• Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise

  2024cites this paper
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime

  2024cites this paper
• Fraud Detection for Random Walks

  2024cites this paper
• Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback

  2024influential citation
• Online Learning in Betting Markets: Profit versus Prediction

  2024influential citation
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits

  2023cites this paper
• Adversarial Contextual Bandits Go Kernelized

  2023cites this paper
• Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance

  2023cites this paper
• Dynamically Interrupting Deadlocks in Game Learning Using Multisampling Multiarmed Bandits

  2023cites this paper
• The “Black-Box” Optimization Problem: Zero-Order Accelerated Stochastic Method via Kernel Approximation

  2023cites this paper
• Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits

  2023cites this paper
• Accelerated Zero-Order SGD Method for Solving the Black Box Optimization Problem Under "Overparametrization" Condition

  2023influential citation
• Anytime Model Selection in Linear Bandits

  2023cites this paper
• Stochastic Adversarial Noise in the "Black Box" Optimization Problem

  2023cites this paper
• Identifying near-optimal decisions in linear-in-parameter bandit models with continuous decision sets

  2022cites this paper
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs

  2022cites this paper
• Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits

  2022influential citation
• Best of Both Worlds Model Selection

  2022cites this paper
• Gradient-Free Optimization for Non-Smooth Saddle Point Problems under Adversarial Noise

  2022cites this paper
• Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game

  2022cites this paper
• Gradient-Free Optimization for Non-Smooth Minimax Problems with Maximum Value of Adversarial Noise

  2022cites this paper
• Top-k eXtreme Contextual Bandits with Arm Hierarchy

  2021cites this paper
• Dueling RL: Reinforcement Learning with Trajectory Preferences

  2021cites this paper
• Majorizing Measures, Sequential Complexities, and Online Learning

  2021cites this paper
• Efficient Bandit Convex Optimization: Beyond Linear Losses

  2021cites this paper
• Stochastic optimization under time drift: iterate averaging, step decay, and high probability guarantees

  2021cites this paper
• Online Markov Decision Processes with Aggregate Bandit Feedback

  2021cites this paper
• Provably Efficient Multi-Task Reinforcement Learning with Model Transfer

  2021cites this paper
• Online Learning in Budget-Constrained Dynamic Colonel Blotto Games

  2021cites this paper
• Computing an Efficient Exploration Basis for Learning with Univariate Polynomial Features

  2021cites this paper
• Bandit Learning for Dynamic Colonel Blotto Game with a Budget Constraint

  2021cites this paper
• Stochastic Optimization under Distributional Drift

  2021cites this paper
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games

  2021cites this paper
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games

  2021influential citation
• Active Online Learning with Hidden Shifting Domains

  2021cites this paper
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously

  2021influential citation
• Stochastic Regret Minimization in Extensive-Form Games

  2020cites this paper
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits

  2020cites this paper
• Active Online Domain Adaptation

  2020cites this paper
• Counterfactual-Free Regret Minimization for Sequential Decision Making and Extensive-Form Games

  2020influential citation
• Efficient Contextual Bandits with Continuous Actions

  2020cites this paper
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs

  2020influential citation
• The Difficult Task of Distribution Generalization in Nonlinear Models

  2020cites this paper
• Online Model Selection for Reinforcement Learning with Function Approximation

  2020cites this paper
• Understanding the role of averaging in non-smooth stochastic gradient descent

  2020cites this paper
• Corralling Stochastic Bandit Algorithms

  2020cites this paper
• Multitask Bandit Learning through Heterogeneous Feedback Aggregation

  2020influential citation
• A Causal Framework for Distribution Generalization

  2020cites this paper
• Stochastic Multi-Player Bandit Learning from Player-Dependent Feedback

  2020cites this paper
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

  2019cites this paper
• Online learning with sparse labels

  2019cites this paper
• Combating adversaries in network-structured security domains

  2018cites this paper
• cient Bandit Combinatorial Optimization Algorithm with Zero-suppressed Binary Decision Diagrams

  2018cites this paper
• On the Generalization Ability of Online Gradient Descent Algorithm Under the Quadratic Growth Condition

  2018cites this paper
• Playing with and against Hedge

  2018cites this paper
• Tight Analyses for Non-Smooth Stochastic Gradient Descent

  2018cites this paper
• A Theory of Model Selection in Reinforcement Learning

  2017cites this paper
• Practical Adversarial Combinatorial Bandit Algorithm via Compression of Decision Sets

  2017cites this paper
• Online multiclass boosting

  2017cites this paper
• Online Convex Optimization with Stochastic Constraints

  2017cites this paper
• Online kernel learning with nearly constant support vectors

  2016cites this paper
• Optimal and Adaptive Online Learning

  2016cites this paper
• Online Combinatorial Optimization under Bandit Feedback

  2016cites this paper
• Structured Stochastic Linear Bandits ( DRAFT )

  2016cites this paper
• Fast Convergence of Common Learning Algorithms in Games

  2016cites this paper
• Learning in Games: Robustness of Fast Convergence

  2016cites this paper
• An efficient high-probability algorithm for Linear Bandits

  2016influential citation
• Worst performance of Hedge in short games

  2015cites this paper
• Optimal and Adaptive Algorithms for Online Boosting Supplementary Material

  2015cites this paper
• Optimal and Adaptive Algorithms for Online Boosting

  2015cites this paper
• Explore no more : Simple and tight high-probability bounds for non-stochastic bandits

  2015cites this paper
• Dependent Online Kernel Learning With Constant Number of Random Fourier Features

  2015cites this paper
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits

  2015cites this paper
• New formulations for active learning

  2014cites this paper
• Maximin effects in inhomogeneous large-scale data

  2014influential citation
• On the Sample Complexity of Random Fourier Features for Online Learning

  2014cites this paper
• Playing against Hedge

  2014cites this paper
• Multiple Optimality Guarantees in Statistical Learning

  2014cites this paper
• Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations

  2013cites this paper
• Online learning in non-stationary Markov decision processes

  2013cites this paper
• Online Learning in Bandit Problems.

  2013influential citation
• Online Learning in a Contract Selection Problem

  2013cites this paper
• Volumetric Spanners: An Efficient Exploration Basis for Learning

  2013cites this paper
• Online tanulás nemstacionárius Markov döntési folyamatokban

  2013cites this paper
• Optimization for Machine Learning

  2013cites this paper
• Building Bridges: Viewing Active Learning from the Multi-Armed Bandit Lens

  2013cites this paper
• Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods

  2012cites this paper
• Contextual Bandit Learning with Predictable Rewards

  2012influential citation
• Searching in the dark: A framework for authenticating unknown users in online social networks

  2012cites this paper
• Interior-Point Methods for Full-Information and Bandit Online Learning

  2012cites this paper
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret

  2012cites this paper
• Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

  2012cites this paper
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

  2012cites this paper