Robbing the bandit: less regret in online geometric optimization against an adaptive adversary

No abstract is available for this paper.

• Publication year

  2006

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2006-01-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1109557.1109660
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient algorithms for online decision problems

  2005cited by this paper
• Contributions to the Theory of Games

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

  2004influential reference
• Adaptive routing with end-to-end feedback: distributed learning and geometric approaches

  2004influential reference
• Online Convex Programming and Generalized Infinitesimal Gradient Ascent

  2003influential reference
• The Nonstochastic Multiarmed Bandit Problem

  2002cited by this paper
• A decision-theoretic generalization of on-line learning and an application to boosting

  1997influential reference
• Gambling in a rigged casino: The adversarial multi-armed bandit problem

  1995cited by this paper
• Aggregating strategies

  1990cited by this paper
• The weighted majority algorithm

  1989influential reference
• 4. APPROXIMATION TO RAYES RISK IN REPEATED PLAY

  1958influential reference
• Some aspects of the sequential design of experiments

  1952cited by this paper

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

  2025cites this paper
• Regret Minimization in Stackelberg Games with Side Information

  2024influential citation
• A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs

  2023cites this paper
• Online Learning for Traffic Navigation in Congested Networks

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

  2022cites this paper
• Non-Stationary Bandits with Auto-Regressive Temporal Dependency

  2022cites this paper
• Contextual Bandits with Large Action Spaces: Made Practical

  2022cites this paper
• A Novel Approach to Address External Validity Issues in Fault Prediction Using Bandit Algorithms

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

  2021cites this paper
• Foundations of Information Theory

  2020cites this paper
• Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits

  2020cites this paper
• Foundations of Probability

  2020cites this paper
• Projection-Free Bandit Optimization with Privacy Guarantees

  2020cites this paper
• The Exp3 Algorithm

  2020cites this paper
• Combinatorial Bandits

  2020cites this paper
• Other Topics

  2020cites this paper
• Follow-the-regularised-Leader and Mirror Descent

  2020cites this paper
• Stochastic Linear Bandits with Sparsity

  2020cites this paper
• Ranking

  2020cites this paper
• Lower Bounds for Bandits with Finitely Many Arms

  2020cites this paper
• High-Probability Lower Bounds

  2020cites this paper
• Contextual Bandits

  2020cites this paper
• Bandits, Probability and Concentration

  2020cites this paper
• Foundations of Convex Analysis

  2020cites this paper
• Stochastic Linear Bandits with Finitely Many Arms

  2020cites this paper
• Optimal Design for Least Squares Estimators

  2020cites this paper
• The Upper Confidence Bound Algorithm

  2020cites this paper
• Stochastic Bandits with Finitely Many Arms

  2020cites this paper
• The Explore-Then-Commit Algorithm

  2020cites this paper
• The Upper Confidence Bound Algorithm: Asymptotic Optimality

  2020cites this paper
• Stochastic Processes and Markov Chains

  2020cites this paper
• Confidence Bounds for Least Squares Estimators

  2020cites this paper
• The Upper Confidence Bound Algorithm: Minimax Optimality

  2020cites this paper
• Contextual and Linear Bandits

  2020cites this paper
• Lower Bounds: Basic Ideas

  2020cites this paper
• Bayesian Bandits

  2020cites this paper
• Thompson Sampling

  2020cites this paper
• Introduction

  2020cites this paper
• Minimax Lower Bounds for Stochastic Linear Bandits

  2020cites this paper
• Preface

  2020cites this paper
• Pure Exploration

  2020cites this paper
• Markov Decision Processes

  2020cites this paper
• Adversarial Bandits with Finitely Many Arms

  2020cites this paper
• Concentration of Measure

  2020cites this paper
• The Exp3-IX Algorithm

  2020cites this paper
• Stochastic Linear Bandits

  2020cites this paper
• Non-stationary Bandits

  2020cites this paper
• Beyond Bandits

  2020cites this paper
• The Upper Confidence Bound Algorithm: Bernoulli Noise

  2020cites this paper
• Bibliography

  2020cites this paper
• Foundations of Bayesian Learning

  2020cites this paper
• Stochastic Bandits

  2020cites this paper
• Adversarial Linear Bandits

  2020cites this paper
• Bandit Algorithms

  2020cites this paper
• Instance-Dependent Lower Bounds

  2020cites this paper
• The Relation between Adversarial and Stochastic Linear Bandits

  2020cites this paper
• Exp3 for Adversarial Linear Bandits

  2020cites this paper
• Asymptotic Lower Bounds for Stochastic Linear Bandits

  2020cites this paper
• Online convex optimization: algorithms, learning, and duality

  2019cites this paper
• Exploration by Optimisation in Partial Monitoring

  2019cites this paper
• Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback

  2019influential citation
• Minimax Lower Bounds

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

  2018influential citation
• General bounds for incremental maximization

  2017cites this paper
• Playing Repeated Network Interdiction Games with Semi-Bandit Feedback

  2017influential citation
• Structured Stochastic Linear Bandits ( DRAFT )

  2016cites this paper
• The computational power of optimization in online learning

  2015cites this paper
• Fighting Bandits with a New Kind of Smoothness

  2015influential citation
• Revenue Optimization against Strategic Buyers

  2015cites this paper
• Online Bandit Learning for a Special Class of Non-Convex Losses

  2015cites this paper
• 8.657: Mathematics of Machine Learning 6. Linear Bandits

  2015cites this paper
• Regret bounded by gradual variation for online convex optimization

  2014cites this paper
• The Blinded Bandit: Learning with Adaptive Feedback

  2014cites this paper
• Concentration of Measure

  2014cites this paper
• High Probability Bounds for Bandit Stochastic and Adversarial Strongly Convex Optimization

  2013cites this paper
• Online Learning with Switching Costs and Other Adaptive Adversaries

  2013cites this paper
• Optimization for Machine Learning

  2013cites this paper
• Online learning for linearly parametrized control problems

  2012cites this paper
• Strategizing surveillance for resource-constrained event monitoring

  2012cites this paper
• Combinatorial Bandits

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

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

  2012cites this paper
• Stochastic Processes and Markov Chains

  2012cites this paper
• Sequential Decision Making in Non-stochastic Environments

  2011cites this paper
• Research Statement Rational Secret Sharing

  2011cites this paper
• The convex optimization approach to regret minimization

  2011cites this paper
• Understanding and Protecting Privacy: Formal Semantics and Principled Audit Mechanisms

  2011cites this paper
• Regret Bound by Variation for Online Convex Optimization

  2011cites this paper
• Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction

  2011cites this paper
• Regret Bounds for the Adaptive Control of Linear Quadratic Systems

  2011cites this paper
• Bandits, Query Learning, and the Haystack Dimension

  2011cites this paper
• Regret Minimizing Audits: A Learning-Theoretic Basis for Privacy Protection

  2011cites this paper
• Predicting Dynamic Difficulty

  2011cites this paper
• Multi-armed bandits on implicit metric spaces

  2011cites this paper
• Return of the Boss Problem: Competing Online against a Non-adaptive Adversary

  2010cites this paper
• Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.

  2010cites this paper
• Expressive models in online learning

  2010cites this paper
• Prediction without loss in multi-armed bandit problems

  2010cites this paper
• Prediction strategies without loss

  2010cites this paper
• Doing OK When the Boss Shows up : Prefix Optimization 1 . 1 Enzo ’ s Order Signups : Prefix Interval Selection

  2010cites this paper