**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 \in \{1,\ldots,k\}$, 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}

Indeed, let $f_\alpha(x) := x^{-\alpha}$, a continuous function with anti-derivative $F_\alpha(x) :=
(1-\alpha)^{-1}x^{1-\alpha}$ if $0 < \alpha < 1$ and $g_1(x):=\log(x)$.
My proof (only sketched here for brevity) of this result is based on the pigeon-hole principle

\begin{eqnarray}
  \begin{split}
    E_{T} &:=\sum_{t=1}^Tf_\alpha(n_t(s_t))\mu(s_t)=\sum_{t=1}^T\sum_{s=1}^k
    f_\alpha(n_t(s))\mu(s)1_{\{s_t=s\}}
    =\sum_{s=1}^k\mu(s)\sum_{t=1}^Tf_\alpha(n_t(s))1_{\{s_t=s\}}\\
    &= \sum_{s=1}^k\mu(s)\sum_{n=1}^{n_T(s)} f_\alpha(n) \le 1-F_\alpha(1) +
\sum_{s=1}^k F_\alpha(n_T(s))\mu(s),
  \end{split}
  \label{eq:ph}
\end{eqnarray}
where the last inequality derives from an [elementary inequality][1] relating a sum and an integral.

I then apply Hoelder's inequality to bound: $\sum_{s=1}^k F_\alpha(n_T(s))\mu(s) \le \|F_\alpha \circ n_T\|_{\frac{1}{1-\alpha}}\|\mu\|_{\frac{1}{\alpha}}$.

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.


  [1]: https://math.stackexchange.com/questions/132521/sum-of-reciprocals-of-square-roots/132527#132527