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(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

• where in the last equality, we have used the trick: $\{n_t(s) \mid s_t=s\} = \{1,2,\ldots,n_T(s)\}$, and

• the last inequality derives from an elementary inequality relating a sum and an integral.

I then apply Hoelder's inequality on the 2nd sum: $\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.