UCLA

Many regret analyses for bandit and reinforcement learning (RL) algorithms contain two steps. The first is to establish confidence bounds for unknown reward functions. The second is a deterministic accounting step that bounds the cumulative contribution of the resulting confidence radii. This thesis develops a unified framework for this second step. The framework treats both full sums over all rounds and selected-subsequence sums, as well as both unclipped and clipped sums. The results are stated in a general reproducing kernel Hilbert space (RKHS) setting and then specialized to finite-dimensional weighted linear designs.