Table of Contents

1  Exploring different doubling tricks for different kinds of regret bounds

1.1  What do we want?

1.2  Dependencies

1.3  Defining the functions \(f\)

1.3.1  Cheating with a “safe” log

1.3.2  Geometric sequences

1.3.3  Exponential sequences

1.3.4  Generic function \(f\)

1.3.5  Some specific case of intermediate sequences

1.4  Defining the sequences and last term

1.4.1  Sequence \(f \mapsto (T_i)_i\)

1.4.2  Last term operator \(T \mapsto L_T\)

1.4.3  Helper for the plot

1.5  Plotting what we want

1.5.1  Plotting the values of the sequences

1.5.2  Plotting the ratio for our upper-bound

1.6  Results

1.6.1  Values of the doubling sequences

1.6.2  Bound in \(R_T \leq \mathcal{O}(\log(T))\)

1.6.3  Bound in \(R_T \leq \mathcal{O}(\sqrt{T})\)

1.6.4  Bound in \(R_T \leq \mathcal{O}(\sqrt{T \log(T)})\)

1.6.5  A last weird bound in \(R_T \leq \mathcal{O}(T^{2/3} \log(T))\) (just to try)

1.7  Conclusions

1.7.1  About geometric sequences

1.7.2  About exponential sequences

1.7.3  About intermediate sequences

Exploring different doubling tricks for different kinds of regret bounds

What do we want?

This notebooks studies and plot the ratio between a sum like the following