A Brief Summary of Upper Bounds for Bandit Problems

This post summarizes the regret analysis for multi-armed bandit problems and linear bandits problems.

Specifically, the Exploration-first / epsilon-greedy algorithm achieves $\tilde{O} (K^{1 / 3} T^{2 / 3})$ regret and UCB obtains $\tilde{O} (\sqrt{K T})$ regret where $K$ is the numberof arms for MAB. For linear bandits, LinUCB obtains $\tilde{O} (σ d \sqrt{T})$ regret where $d$ is the feature dimension. Let us start with the multi-armed bandit (MAB) problems!

1. Multi-armed bandit (MAB) problems

In MAB, we have $K$ actions (the “arms”) and when we play arm $i \in {1, 2, \dots, K}$ we obtain a random reward $r_{i}$ which has mean reward:

E [r_{i}] = μ_{i}, | μ_{i} | \leq 1.

Every iteration $t$ , the learner will pick an arm $A_{t} \in [1, 2, \dots, K]$ . The regret is defined as:

R_{T} = T \cdot max_{i} μ_{i} - \sum_{t = 1}^{T} μ_{A_{t}} .

The goal is to minimize the regret.

1.1 Exploration-first algorithm

Algorithm 1: Exploration-first

Spend the first N step exploring, where each action is played for N/K times. The corresponding estimates for each action a is: ${\hat{Q}}_{t} (a) = \frac{\sum_{i = 1}^{t} R_{i} \cdot 1 [A_{i} = a]}{\sum_{i = 1}^{t} 1 [A_{i} = a]}, a \in [K]$
For t = N+1,...,T: $A_{t} := {argmax}_{a} {\hat{Q}}_{t} (a)$

Analysis of the Exploration-first algorithm

$Step1.$ For any $t \geq N$ , by Hoeffding’s inequality and an union bound, w.p. $1 - δ$

sup_{a \in [K]} | \hat{Q} (a) - μ_{a} | \leq \sqrt{\frac{K}{2 N} \log (2 K / δ)} := ϵ

$Step2.$ Regret for the Exploration phase:

R_{1 : N} \leq \frac{N}{K} \sum_{a \in [K]} (max_{a^{'}} μ_{a^{'}} - μ_{a}) \leq N

$Step3.$ Regret for the Exploitation phase $A_{t} \equiv {\hat{a}}^{⋆} = {argmax}_{a} \hat{Q} (a)$ :

\begin{aligned} R_{N + 1 : T} \leq (T - N) \cdot (μ_{a^{⋆}} - μ_{{\hat{a}}^{⋆}}) \\ = & (T - N) [μ_{a^{⋆}} - \hat{Q} (a^{⋆}) + \hat{Q} (a^{⋆}) - \hat{Q} ({\hat{a}}^{⋆}) + \hat{Q} ({\hat{a}}^{⋆}) - μ_{{\hat{a}}^{⋆}}] \\ \leq & (T - N) [ϵ + 0 + ϵ] \end{aligned}

$Step4.$ The total regret is

R_{T} = N + 2 T \sqrt{\frac{K}{2 N} \log (2 k / δ)} = O (T^{2 / 3} K^{1 / 3} (\log (2 K / δ))^{1 / 3})

where the last equal sign chooses $N = T^{2 / 3} K^{1 / 3} (\log (2 K / δ))^{1 / 3}$ .

1.2 Epsilon-greedy algorithm

Algorithm 2: Epsilon-greedy

Let the strategy be:

With probability $ϵ$ , choose the action uniformly at random;
With probability $1 - ϵ$ , select

A_{t} := {argmax}_{a \in [K]} {\hat{Q}}_{t} (a),

where ${\hat{Q}}_{t}$ is defined the same as Algorithm 1.

It can be shown the regret bound is

\underset{Exploration}{\underset{⏟}{ϵ T}} + \underset{Exploitation}{\underset{⏟}{\sum_{t = 1}^{T} C \sqrt{\frac{K}{ϵ t}}}}

choose $ϵ = T^{- 1 / 3} K^{1 / 3}$ gives regret $\tilde{O} (T^{2 / 3} K^{1 / 3})$ .

1.3 Upper Condifence Bound (UCB) Algorithm

Optimism in the face of uncertainty: UCB

Algorithm 3: UCB

Play each action $a \in [K]$ once (in total $K$ steps);
For $t = k + 1, \dots, T$
- Choose $A_{t} := {argmax}_{a} {\hat{Q}}_{t} (a) + \sqrt{\frac{2 \log (2 T K / δ)}{2 N_{t} (a)}};$
- where ${\hat{Q}}_{t} (a) = \frac{1}{N_{t} (a)} (R_{a} + \sum_{i = k + 1}^{t - 1} 1 [A_{i} = a] \cdot R_{i})$ , $N_{t} (a) = \sum_{i = 1}^{t - 1} 1 [A_{i} = a]$ .

Regret analysis: non-adaptive bound

By Azuma-Hoeffding’s inequality and an union bound, w.p. $1 - δ$ ,

| R_{a} - μ_{a} + \sum_{i = k + 1}^{t - 1} 1 [A_{i} = a] \cdot (R_{i} - μ_{a}) | \leq \sqrt{2 N_{t} (a) \log (K T / δ)}, \forall a \in [K], t \in [k + 1, T]

Note the above is equivalent to

\begin{aligned} sup_{t, a} \frac{1}{\sqrt{N_{t} (a)}} | R_{a} - μ_{a} + \sum_{i = k + 1}^{t - 1} 1 [A_{i} = a] \cdot (R_{i} - μ_{a}) | \leq \sqrt{2 \log (K T / δ)} \\ \Leftrightarrow & sup_{t, a} \sqrt{N_{t} (a)} \cdot | {\hat{Q}}_{t} (a) - μ_{a} | \leq \sqrt{2 \log (K T / δ)} \\ \Leftrightarrow & | {\hat{Q}}_{t} (a) - μ_{a} | \leq \sqrt{\frac{2 \log (K T / δ)}{N_{t} (a)}}, \forall a \in [K], t \end{aligned}

Recall ${\bar{Q}}_{t} (a) = {\hat{Q}}_{t} (a) + \sqrt{\frac{2 \log (2 K T / δ)}{N_{t} (a)}}$ , then at each time $t$ ,

\begin{aligned} μ_{a^{⋆}} - μ_{A_{t}} \\ = & μ_{a^{⋆}} - {\bar{Q}}_{t} (a^{⋆}) + {\bar{Q}}_{t} (a^{⋆}) - {\bar{Q}}_{t} (A_{t}) + {\bar{Q}}_{t} (A_{t}) - μ (A_{t}) \\ \leq & 0 + 0 + 2 \sqrt{\frac{2 \log (K T / δ)}{N_{t} (a)}} \end{aligned}

which uses optimism and the UCB rule. Then the total regret is bounded by

\begin{aligned} R_{T} = & R_{1 : K} + R_{K + 1 : T} \\ \leq & K + \sum_{t = K + 1}^{T} (μ_{a^{⋆}} - μ_{A_{t}}) \\ \leq & K + \sum_{t = K + 1}^{T} 2 \sqrt{\frac{2 \log (K T / δ)}{N_{t} (a)}} \\ \leq & K + 2 \sqrt{2 \log (K T / δ)} \sum_{a = 1}^{K} \sum_{i = 1}^{N_{T} (a)} \frac{1}{\sqrt{i}} \\ \leq & K + 4 \sqrt{2 \log (K T / δ)} \sum_{a = 1}^{K} \sqrt{N_{T} (a)} eqn (⋆) \\ \leq & K + 4 \sqrt{2 \log (K T / δ)} \sqrt{K \cdot \sum_{a = 1}^{K} N_{T} (a)} \\ = & K + 4 \sqrt{2 K T \log (K T / δ)} \end{aligned}

Regret analysis: gap-dependent expression

Define the gap $Δ_{a} := μ_{a^{⋆}} - μ_{a}$ . By the concentration result and the UCB rule, we know

\begin{aligned} {\bar{Q}}_{t} (a) \leq & μ_{a} + \sqrt{\frac{2 \log (2 T K / δ)}{N_{t} (a)}} \\ = & μ_{a^{⋆}} - Δ_{a} + \sqrt{\frac{2 \log (2 T K / δ)}{N_{t} (a)}} \\ \Leftrightarrow & μ_{a^{⋆}} - {\bar{Q}}_{t} (a) \geq Δ_{a} - \sqrt{\frac{2 \log (2 T K / δ)}{N_{t} (a)}} \end{aligned}

Note when $μ_{a^{⋆}} - {\bar{Q}}_{t} (a) \geq 0$ , then arm $a$ will never be played again (since ${\bar{Q}}_{t} (a^{⋆})$ always upper bounds ${\bar{Q}}_{t} (a)$ ) and $N_{t} (a)$ will no longer change! Therefore from above we always have

0 \geq Δ_{a} - \sqrt{\frac{2 \log (2 T K / δ)}{N_{T} (a)}} \Leftrightarrow N_{T} (a) \leq \frac{2 \log (2 T K / δ)}{Δ_{a}^{2}}

The former non-adaptive bound can be replaced by

R_{T} = \sum_{a = 1}^{K} Δ_{a} + O (\sum_{a \neq a^{⋆}} \frac{1}{Δ_{a}} \log (K T / δ))

$Short note:$ for the non-stochastic bandit setting (e.g. adversarial setting), there are algorithms (e.g. EXP3) that achieves the same regret. See Peter Auer et al. (2001).

2. Linear Bandits

The problem setup

Action space is a compact set $x_{t} \in D \subset R^{d}$ ;
Reward is linear with i.i.d mean-zero $σ^{2}$ -subguassian noise:

$r_{t} = μ^{⋆} \cdot x_{t} + η_{t}, E [r_{t} | x_{t} = x] = μ^{⋆} \cdot x \in [- 1, 1];$

Agent chooses a sequence of actions $x_{1}, \dots, x_{T}$ ;
Let $x^{⋆} \in {argmax}_{x \in D} μ^{⋆} \cdot x$ , then the regret is defined as

R_{T} = T \cdot ⟨ μ^{⋆}, x^{⋆} ⟩ - \sum_{t = 1}^{T} ⟨ μ^{⋆}, x_{t} ⟩ .

2.1. LinUCB Algorithm

For each time $t$ , with collected data $(x_{i}, r_{i})$ for all $i = 1, \dots, t - 1$

Compute the estimated ${\hat{μ}}_{t}$ through ridge regression:

{\hat{μ}}_{t} := {argmin}_{θ} \sum_{i = 1}^{t - 1} (x_{i}^{⊤} θ - r_{i})^{2} + λ | | θ | |_{2}^{2}

Define $Σ_{t} = λ I + \sum_{i = 1}^{t - 1} x_{i} x_{i}^{⊤}$ , then ${\hat{μ}}_{t} := Σ_{t}^{- 1} \sum_{i = 1}^{t - 1} r_{i} x_{i}$

Construct high probability confidence ellipsoid of the parameter

{Ball}_{t} = {μ | (μ - {\hat{μ}}_{t})^{⊤} Σ_{t} (μ - {\hat{μ}}_{t}) \leq β_{t}}

Choose actions that maximize the UCB

x_{t} = {argmax}_{x \in D} max_{μ \in {Ball}_{t}} ⟨ x, μ ⟩

$Note:$ the computation of LinUCB could be NP-hard though.

Theorem (Upper bound of LinUCB) Choose $β_{t} = \tilde{O} (σ^{2} \cdot d)$ , suppose $‖ μ^{⋆} ‖ \leq W$ , $‖ x ‖ \leq B$ for all $x \in D$ . Then set $λ = σ^{2} / W^{2}$ , w.p. $1 - δ$ ,

R_{T} \leq C σ \sqrt{T} (d \log (1 + \frac{T B^{2} W^{2}}{d σ^{2}}) + \log (4 / δ)) .

2.2 Analysis of the LinUCB algorithm

The analysis is based on several lemmas.

Lemma 1: “Width” of confidence ball Let $x \in D$ . If $μ \in {Ball}_{t}$ , then

| (μ - {\hat{μ}}_{t})^{⊤} x | \leq \sqrt{β_{t} x^{⊤} Σ_{t}^{- 1} x}

Lemma 2: Instaneous regret is bounded Fix $t \leq T$ and define $w_{t} := \sqrt{x_{t}^{⊤} Σ_{t}^{- 1} x_{t}}$ . If $μ^{⋆} \in {Ball}_{t}$ , then

{regret}_{t} \leq 2 min (\sqrt{β_{t}} w_{t}, 1) \leq 2 \sqrt{β_{T}} min (w_{t}, 1) .

Lemma 3: “Geometric potential” argument We have:

det Σ_{T} = det Σ_{0} \cdot \prod_{t = 0}^{T - 1} (1 + w_{t}^{2}) .

$Note:$ The proof of this lemma is intersting, see Lemma 5.9 of AJKS.

Lemma 4 For any sequence $x_{0}, \dots, x_{T - 1}$ such that for $t < T$ , $‖ x_{t} ‖_{2} \leq B$ , then

\log (det Σ_{T - 1} / det Σ_{0}) = \log det (I + \frac{1}{λ} \sum_{t = 0}^{T - 1} x_{t} x_{t}^{⊤}) \leq d \log (1 + \frac{T B^{2}}{d λ}) .

Combine Lemma 1-4, we have for LinUCB if $μ^{⋆} \in {Ball}_{t}$ for all $t$ , then

$\begin{matrix} (1) & \sum_{t = 0}^{T - 1} {regret}_{t}^{2} \leq 4 β_{T} d \log (1 + \frac{T B^{2}}{d λ}) \end{matrix}$

Also, it can be shown for $δ > 0$ , $P (\forall t, μ^{⋆} \in {Ball}_{t}) \geq 1 - δ$ .

Combine $(1)$ and the above we can show w.p. $1 - δ$ ,

R_{T} = \sum_{t = 0}^{T - 1} {regret}_{t} \leq \sqrt{T \sum_{t = 0}^{T - 1} {regret}_{t}^{2}} \leq \sqrt{4 T β_{T} d \log (1 + \frac{T B^{2}}{d λ})}

which finishes the proof.

The content of this post mainly comes from the Bandit Algorithms Book and AJKS.