Skip to content

Bandit Algorithms

Primary menu

Category: Bandits

Bayesian/minimax duality for adversarial bandits

Posted onMarch 17, 2019March 7, 20201 Comment

The Bayesian approach to learning starts by choosing a prior probability distribution over the unknown parameters of the world. Then, as the learner makes observation, the prior is updated using Bayes rule to form the posterior, which represents the new Continue Reading

CategoriesAdversarial bandits, Bandits, Bayesian bandits, Game theory

The variance of Exp3

Posted onFebruary 16, 2019March 17, 2019Leave a comment

In an earlier post we analyzed an algorithm called Exp3 for $k$-armed adversarial bandits for which the expected regret is bounded by \begin{align*} R_n = \max_{a \in [k]} \E\left[\sum_{t=1}^n y_{tA_t} – y_{ta}\right] \leq \sqrt{2n k \log(k)}\,. \end{align*} The setting of Continue Reading

CategoriesAdversarial bandits, Bandits, Lower bound

First order bounds for k-armed adversarial bandits

Posted onFebruary 16, 2019October 28, 20214 Comments

To revive the content on this blog a little we have decided to highlight some of the new topics covered in the book that we are excited about and that were not previously covered in the blog. In this post Continue Reading

CategoriesAdversarial bandits, Bandits, Finite-armed bandits

Bandit Algorithms Book

Posted onJuly 27, 2018September 10, 20192 Comments

Dear readers After nearly two years since starting to write the blog we have at last completed a first draft of the book, which is to be published by Cambridge University Press. The book is available for free as a Continue Reading

CategoriesBandits

Bandit tutorial slides and update on book

Posted onFebruary 9, 2018March 12, 20192 Comments

This website has been quiet for some time, but we have not given up on bandits just yet. First up, we recently gave a short tutorial at AAAI that covered the basics of finite-armed stochastic bandits and stochastic linear bandits. Continue Reading

CategoriesBandits

Adversarial linear bandits and the curious case of the unit ball

Posted onNovember 25, 2016March 17, 2019Leave a comment

According to the main result of the previous post, given any finite action set $\cA$ with $K$ actions $a_1,\dots,a_K\in \R^d$, no matter how an adversary selects the loss vectors $y_1,\dots,y_n\in \R^d$, as long as the action losses $\ip{a_k,y_t}$ are in Continue Reading

CategoriesAdversarial bandits, Bandits, Lower bound

Adversarial linear bandits

Posted onNovember 24, 2016March 17, 20191 Comment

In the next few posts we will consider adversarial linear bandits, which, up to a crude first approximation, can be thought of as the adversarial version of stochastic linear bandits. The discussion of the exact nature of the relationship between Continue Reading

CategoriesAdversarial bandits, Bandits

Sparse linear bandits

Posted onNovember 21, 20161 Comment

In the last two posts we considered stochastic linear bandits, when the actions are vectors in the $d$-dimensional Euclidean space. According to our previous calculations, under the condition that the expected reward of all the actions are in a fixed Continue Reading

CategoriesBandits

Ellipsoidal Confidence Sets for Least-Squares Estimators

Posted onNovember 13, 20168 Comments

Continuing the previous post, here we give a construction for confidence bounds based on ellipsoidal confidence sets. We also put things together and show bound on the regret of the UCB strategy that uses the constructed confidence bounds. Constructing the Continue Reading

CategoriesBandits

Lower Bounds for Stochastic Linear Bandits

Posted onOctober 20, 2016March 17, 20192 Comments

Lower bounds for linear bandits turn out to be more nuanced than the finite-armed case. The big difference is that for linear bandits the shape of the action-set plays a role in the form of the regret, not just the Continue Reading

CategoriesBandits, Lower bound

Post navigation

← Older posts
  • About
  • Download book

Recent Posts

  • Bayesian/minimax duality for adversarial bandits
  • The variance of Exp3
  • First order bounds for k-armed adversarial bandits
  • Bandit Algorithms Book
  • Bandit tutorial slides and update on book

Recent Comments

  • Tor Lattimore on Ellipsoidal Confidence Sets for Least-Squares Estimators
  • Zeyad on Ellipsoidal Confidence Sets for Least-Squares Estimators
  • Tiancheng Yu on Bayesian/minimax duality for adversarial bandits
  • Claire on Ellipsoidal Confidence Sets for Least-Squares Estimators
  • Tor Lattimore on Ellipsoidal Confidence Sets for Least-Squares Estimators

Archives

  • March 2019
  • February 2019
  • July 2018
  • February 2018
  • November 2016
  • October 2016
  • September 2016
  • August 2016

Categories

  • Adversarial bandits
  • Bandits
  • Bayesian bandits
  • Finite-armed bandits
  • Game theory
  • Lower bound
  • Probability

Meta

  • Log in
  • Entries RSS
  • Comments RSS
  • WordPress.org
Copyright © 2023 Bandit Algorithms. All Rights Reserved.
Clean Education by Catch Themes
Scroll Up
Bitnami