Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try...

So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the need to devise and proof the following small theorem.

[A small Theorem] Consider $T \ge 1$ runs of an experiment with $k \ge 1$ possible outcomes, only one of which can be the observed on each run. For each run $t$, let $s_t \in \{1,\ldots,k\}$ be observed outcome. For each possible outcome $s$, let $n_t(s):=\sum_{t' \le t} 1_{\{s_{t'} = s\}}$ be the total number of observations of $s$ in the first $t$ runs of the experiment. Finally, let $\mu \in \Delta_k$ be any prior distribution on the outcomes, and let $\alpha \in (0, 1]$. Define $E_{T}:=\sum_{t=1}^T n_t(s_t)^{-\alpha}\mu(s_t)$. We have the bound \begin{eqnarray} E_{T} \le \begin{cases}\frac{1}{1-\alpha}\left(\|\mu\|_{\frac{1}{\alpha}}T^{1-\alpha}-\alpha \right) = \mathcal O\left(\frac{1}{1-\alpha}\|\mu\|_{\frac{1}{\alpha}}T^{1-\alpha}\right), &\mbox{ if }0 < \alpha < 1,\\ \log(T)+ 1=\mathcal O(\log(T)),&\mbox{ if }\alpha = 1.\end{cases} \end{eqnarray}

My proof (not provided here for brevity) of this result is based on the pigeon-hole principle and certain careless applications of Hoelder's inequality. Question

• Are there general tools (transforms, general inequalities, techniques, etc.) for handling quantities like $E_{T}:=\sum_{t=1}^T n_t(s_t)^{-\alpha}\mu(s_t)$ defined in the above theorem ?

• Do the above above bounds on $E_T$ look right ? Are they alarmly off ?

Any kind of feedback, input, etc. will be really appreciated. Thanks.