BanditAlgorithm.adversarial_bandit_exp3ix_high_probability_regret_tuned

Setup (all notions unfolded from the underlying definitions). Fix an arm count $k$ and write $[k]=\{0,\dots,k-1\}$. A history of length $m$ is a sequence of pairs $(a_t, r_t) \in [k]\times\mathbb{R}$, $t < m$; a policy $\pi$ gives, for each $m$ and each length-$m$ history $h$, a probability measure $\pi_m(h)$ on $[k]$, measurably in $h$. Given a reward table $x = (x_t(i))_{t\in\mathbb{N},\,i\in[k]}$ of reals, the $n$-round adversarial law $\mathbb{P}^n_{x,\pi}$ on length-$n$ histories is defined recursively: $\mathbb{P}^0$ is the point mass at the empty history, and $\mathbb{P}^{m+1}$ is the law of $h$ extended by the pair $(A,\, x_m(A))$, where $h \sim \mathbb{P}^m$ and $A \sim \pi_m(h)$ — the reward recorded at round $m$ is deterministically $x_m(A)$.

For real parameters $\eta, \gamma$, the Exp3-IX estimates and probabilities are defined by the joint recursion $\hat T_0 \equiv 0$ and

where $h'$ is the length-$m$ prefix of $h$ and $(a,r)$ its last entry (only the played arm's coordinate is incremented, by the $\gamma$-shifted importance-weighted quantity $1-r$; the softmax uses the negated scaled estimates). "$\pi$ is an Exp3-IX($\eta,\gamma$) policy" means: $\pi_m(h) = \sum_{i\in[k]} Q_m(h)(i)\,\delta_i$ for every $m \in \mathbb{N}$ and every length-$m$ history $h$ (reachable or not), the nonnegative weights being read into $[0,\infty]$.

The pathwise regret of a length-$n$ history $h$ with recorded rewards $r_0,\dots,r_{n-1}$ is

(the first term is a real-valued supremum over the finite arm set, a genuine maximum since $k \ge 2$ under the hypotheses below; the second is the sum of the rewards recorded in $h$).

Assertion. With the confidence-dependent learning rate $\eta = \sqrt{\dfrac{\log k + \log\frac{k+1}{\delta}}{n\,k}}$ and $\gamma = \eta/2$, the theorem claims that the $\mathbb{P}^n_{x,\pi}$-probability of the set of length-$n$ histories $h$ satisfying

is at most $\delta$:

Hypotheses:

• $k \in \mathbb{N}$ with $1 < k$; $n \in \mathbb{N}$ with $0 < n$.
• $x_t(i) \in [0,1]$ (closed interval) for every round $t \in \mathbb{N}$ — not only $t < n$ — and every arm $i \in [k]$.
• $\delta \in (0,1)$ (open interval at both ends).
• $\eta$ is equal (by hypothesis) to $\sqrt{\big(\log k + \log((k+1)/\delta)\big)/(nk)}$ — note this tuning depends on $\delta$, unlike the untuned sibling theorem.
• $\pi$ is any policy satisfying the Exp3-IX($\eta$, $\eta/2$) predicate.

Edge cases and caveats:

• The probability on the left is a value in $[0,\infty]$; the right-hand side is the embedding of the real $\delta$ into $[0,\infty]$ (no truncation, since $0 < \delta$).
• The event uses a non-strict inequality: histories whose pathwise regret is at least the threshold; histories with regret exactly equal to the threshold are included.
• $k+1$ inside the logarithms is the real number $k+1$ (cast of the natural $k$, plus one); since $k \ge 2$ and $0<\delta<1$, all logarithms appearing ($\log(k+1)$, $\log(1/\delta)$, $\log((k+1)/\delta)$, $\log k$) are positive, and $\sqrt{\cdot}$ (the real square root, $0$ on negatives) is applied to positive quantities.
• $\delta$ ranges over the open interval: $\delta = 0$ and $\delta = 1$ are excluded.
• Both the learning rate $\eta$ and the exploration shift $\gamma = \eta/2$ are pinned exactly; nothing is claimed for other tunings.
• The Exp3-IX predicate constrains $\pi$ at every history of every length, including unreachable ones; the theorem is universally quantified over policies satisfying it and does not itself assert existence of one.
• The pathwise regret evaluates the rewards recorded in the history (which under $\mathbb{P}^n_{x,\pi}$ almost surely equal $x_t(A_t)$), and compares against the best single arm in hindsight.