Let Z 1 , Z 2 , . . . , Z n Z_1, Z_2, ..., Z_n Z 1 , Z 2 , ... , Z n Z Z Z [ 0 , 1 ] [0, 1] [ 0 , 1 ]
μ k ≐ 1 k ∑ i = 1 k Z i \mu_k \doteq \frac{1}{k} \sum_{i = 1}^k Z_i μ k ≐ k 1 ∑ i = 1 k Z i 1 ≤ k ≤ n 1 \le k \le n 1 ≤ k ≤ n
μ = E [ Z ] \mu = \mathbb{E}[Z] μ = E [ Z ]
M k M_k M k
M k ≐ { μ k + log 1 δ 2 k ≤ μ } ,
M_k \doteq \left\{ \mu_k + \sqrt{ \frac{ \log \frac{1}{\delta} }{2 k} } \le \mu \right\},
M k ≐ ⎩ ⎨ ⎧ μ k + 2 k log δ 1 ≤ μ ⎭ ⎬ ⎫ , where 0 < δ < 1 0 < \delta < 1 0 < δ < 1
We are interested in bounding the probability of
Pr [ ∪ k = 1 n M k ] .
\Pr[ \cup_{k = 1}^n M_k ].
Pr [ ∪ k = 1 n M k ] . Hoeffding Inequality
We first prove a bound of
Pr [ ∪ k = 1 n M k ] ≤ n δ
\Pr[ \cup_{k = 1}^n M_k ] \le n \delta
Pr [ ∪ k = 1 n M k ] ≤ n δ by Hoeffding inequality.
Hoeffding Inequality. For a fixed integer s s s Z 1 , Z 2 , . . . , Z s Z_1, Z_2, ..., Z_s Z 1 , Z 2 , ... , Z s Z Z Z [ 0 , 1 ] [0, 1] [ 0 , 1 ] r > 0 r > 0 r > 0
Pr [ μ − μ s ≥ r ] ≤ exp ( − 2 s r 2 ) .
\Pr[ \mu - \mu_s \ge r] \le \exp(- 2 s r^2 ). \\
\
Pr [ μ − μ s ≥ r ] ≤ exp ( − 2 s r 2 ) . Applying Hoeffding inequality with s = k s = k s = k r = log 1 δ 2 k r = \sqrt{ \frac{ \log \frac{1}{\delta} }{2 k} } r = 2 k l o g δ 1
Pr [ M k ] ≤ δ .
\Pr[ M_k ] \le \delta.
Pr [ M k ] ≤ δ . By sub-additivity of probability,
Pr [ ∪ k = 1 n M k ] ≤ ∑ k = 1 n Pr [ M k ] = n δ .
\Pr[ \cup_{k = 1}^n M_k ] \le \sum_{k = 1}^n \Pr[M_k] = n \delta.
Pr [ ∪ k = 1 n M k ] ≤ k = 1 ∑ n Pr [ M k ] = n δ . To make the bound meaningful, we require that δ ≤ 1 n \delta \le \frac{1}{n} δ ≤ n 1
Beyond The Naive Union Bound
In this section, we avoid using union bound over n n n Pr [ ∪ k = 1 n M k ] \Pr[ \cup_{k = 1}^n M_k ] Pr [ ∪ k = 1 n M k ]
Pr [ ∪ k = 1 n M k ] ≤ ( log 1 α n + 1 ) ⋅ δ α ,
\Pr[ \cup_{k = 1}^n M_k ] \le ( \log_\frac{1}{\alpha} n + 1 ) \cdot \delta^\alpha,
Pr [ ∪ k = 1 n M k ] ≤ ( log α 1 n + 1 ) ⋅ δ α , where α \alpha α 0 < α < 1 0 < \alpha < 1 0 < α < 1
As a sanity check, suppose δ = 1 n \delta = \frac{1}{n} δ = n 1 α = 1 2 \alpha = \frac{1}{2} α = 2 1
Pr [ ∪ k = 1 n M k ] ≤ n δ = 1 ,
\Pr[ \cup_{k = 1}^n M_k ] \le n \delta = 1,
Pr [ ∪ k = 1 n M k ] ≤ n δ = 1 , which is trivial.
( log 1 α n + 1 ) ⋅ δ α = ( log 2 n + 1 ) ⋅ 1 n
\begin{aligned}
( \log_\frac{1}{\alpha} n + 1 ) \cdot \delta^\alpha
&= (\log_2 n + 1) \cdot {1 \over \sqrt n}
\end{aligned}
( log α 1 n + 1 ) ⋅ δ α = ( log 2 n + 1 ) ⋅ n 1
The proof relies on a strengthened version of Hoeffding inequality.
Fact [1]. For a fixed integer s s s Z 1 , Z 2 , . . . , Z s Z_1, Z_2, ..., Z_s Z 1 , Z 2 , ... , Z s Z Z Z [ 0 , 1 ] [0, 1] [ 0 , 1 ] r > 0 r > 0 r > 0
Pr [ ∃ t ≤ s : t ⋅ μ − t ⋅ μ t ≥ r ] ≤ exp ( − 2 r 2 s ) .
\Pr[ \exists t \le s : \quad t \cdot \mu - t \cdot \mu_t \ge r] \le \exp(- \frac{2 r^2}{s} ). \\
\
Pr [ ∃ t ≤ s : t ⋅ μ − t ⋅ μ t ≥ r ] ≤ exp ( − s 2 r 2 ) . Proof. We divide the M k M_k M k ⌊ log 1 α n ⌋ + 1 \lfloor \log_\frac{1}{\alpha} n \rfloor + 1 ⌊ log α 1 n ⌋ + 1 0 ≤ j ≤ ⌊ log 1 α n ⌋ 0 \le j \le \lfloor \log_\frac{1}{\alpha} n \rfloor 0 ≤ j ≤ ⌊ log α 1 n ⌋
B j ≐ ∪ n ⋅ α j + 1 < k ≤ n ⋅ α j M k = { ∃ n ⋅ α j + 1 < k ≤ n ⋅ α j , μ k + log 1 δ 2 k ≤ μ } = { ∃ n ⋅ α j + 1 < k ≤ n ⋅ α j , k ⋅ μ k + k log 1 δ 2 ≤ k ⋅ μ } ⊂ { ∃ n ⋅ α j + 1 < k ≤ n ⋅ α j , k ⋅ μ k + n ⋅ α j + 1 log 1 δ 2 ≤ k ⋅ μ }
\begin{aligned}
B_j &\doteq \cup_{n \cdot \alpha^{j + 1} < k \le n \cdot \alpha^j } M_k \\
&= \left\{ \exists \quad n \cdot \alpha^{j + 1} < k \le n \cdot \alpha^j, \mu_k + \sqrt{ \frac{ \log \frac{1}{\delta} }{2 k} } \le \mu \right\} \\
&= \left\{ \exists \quad n \cdot \alpha^{j + 1} < k \le n \cdot \alpha^j, k \cdot \mu_k + \sqrt{ \frac{ k \log \frac{1}{\delta} }{2} } \le k \cdot \mu \right\} \\
&\subset \left\{ \exists \quad n \cdot \alpha^{j + 1} < k \le n \cdot \alpha^j, k \cdot \mu_k + \sqrt{ \frac{ n \cdot \alpha^{j + 1} \log \frac{1}{\delta} }{2} } \le k \cdot \mu \right\} \\
\end{aligned}
B j ≐ ∪ n ⋅ α j + 1 < k ≤ n ⋅ α j M k = ⎩ ⎨ ⎧ ∃ n ⋅ α j + 1 < k ≤ n ⋅ α j , μ k + 2 k log δ 1 ≤ μ ⎭ ⎬ ⎫ = ⎩ ⎨ ⎧ ∃ n ⋅ α j + 1 < k ≤ n ⋅ α j , k ⋅ μ k + 2 k log δ 1 ≤ k ⋅ μ ⎭ ⎬ ⎫ ⊂ ⎩ ⎨ ⎧ ∃ n ⋅ α j + 1 < k ≤ n ⋅ α j , k ⋅ μ k + 2 n ⋅ α j + 1 log δ 1 ≤ k ⋅ μ ⎭ ⎬ ⎫ Applying Fact [1] with s = ⌊ n ⋅ α j ⌋ < n ⋅ α j s = \lfloor n \cdot \alpha^j \rfloor < n \cdot \alpha^j s = ⌊ n ⋅ α j ⌋ < n ⋅ α j r = n ⋅ α j + 1 log 1 δ 2 r = \sqrt{ \frac{ n \cdot \alpha^{j + 1} \log \frac{1}{\delta} }{2 } } r = 2 n ⋅ α j + 1 l o g δ 1
Pr [ B j ] ≤ exp ( − n ⋅ α j + 1 log 1 δ 2 2 n ⋅ α j ) = δ α .
\Pr[B_j] \le \exp( - \frac{ n \cdot \alpha^{j + 1} \log \frac{1}{\delta} }{2} \frac{ 2 }{ n \cdot \alpha^j } ) = \delta^{ \alpha }.
Pr [ B j ] ≤ exp ( − 2 n ⋅ α j + 1 log δ 1 n ⋅ α j 2 ) = δ α . Summing over all possible values of j j j
Pr [ ∪ j = 0 ⌊ log 1 α n ⌋ B j ] ≤ ∑ j = 0 ⌊ log 1 α n ⌋ Pr [ B j ] ≤ ( log 1 α n + 1 ) ⋅ δ α .
\Pr[ \cup_{j = 0}^{ \lfloor \log_\frac{1}{\alpha} n \rfloor } B_j] \le \sum_{j = 0}^{ \lfloor \log_\frac{1}{\alpha} n \rfloor } \Pr[B_j] \le( \log_\frac{1}{\alpha} n + 1 ) \cdot \delta^\alpha.
Pr [ ∪ j = 0 ⌊ l o g α 1 n ⌋ B j ] ≤ j = 0 ∑ ⌊ l o g α 1 n ⌋ Pr [ B j ] ≤ ( log α 1 n + 1 ) ⋅ δ α . Remark: The first inequality still follows from union bound. However the number of events is now bounded by log 1 α n + 1 \log_\frac{1}{\alpha} n + 1 log α 1 n + 1 n n n δ \delta δ δ α \delta^\alpha δ α
Reference
[1] S. Lattimore, “Bandit Algorithms,”
← Back to all notes Back to top ↑