In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify a choice of action $x_t \sim p_t$ from some specified probability distribution $p_t$ and observe $l_{t}(x_t)$.
Been reading this blog post https://blogs.princeton.edu/imabandit/2016/08/06/kernel-based-methods-for-bandit-convex-optimization-part-1/ accompanying the paper https://arxiv.org/abs/1607.03084. The core idea is to estimate the objective(loss) function $l_{t}$ with $\tilde{l_{t}}$ using the feed back from a single-point evaluation of $l_{t}$ at $x_t$. When they estimate the regret from this procedure they use $\langle p_t - q, \tilde{l}_t \rangle$, where $p_t$ is a distribution(strategy on how to sample from the decision space) and $q$ is just a random strategy. But the problem is that the choice of $p_t$ has nothing to do with $x_t$ and $l_t(x_t)$ because $p_t$ has to be specified before $l_t(x_t)$ was able to be observed, and it purely depends on past objectives. Intuitively $l_t$ can be dramatically different from $l_{t - i}$. Then how can we get a good choice of $x_t$ based purely on point observations from $l_{t-i}$?
To make my question more precise, it is not clear on they throw away the term $l_t(x)$ in the following inequality on page 9 right below inequality (10):
$E_{x_t \sim K_t p_t}(p_t, \tilde{l}_{t}^{2}) = \int K_{t}p_t(x)p_t(y) \frac{l_t(x)^2}{(K_tp_t(x))^2}dy dx \leq \int \frac{K^{(2)}_{t}p_t(x)}{K_tp_t(x)}dx \leq C$.
A convex function must be bounded on a compact set but I do not see how you can bound them uniformly. Even if they are, this does not seem like an ideal bound to my mind.
