I was going through this course on reinforcement learning (the course has two lecture videos and corresponding slides) and I had a doubt. On slide 18 of this pdf, it states following condition for an algorithm to have regret sublinear in T (T being number of pulls of multi arm bandit).

C2 - Greedy in the Limit: Let exploit(T) denote the number of pulls that are that are greedy w.r.t the empirical mean up to horizon $T$. For sub-linear regret, we need $$\lim_{T\rightarrow\infty}\frac{\mathbb{E}[exploit(T)]}{T}=1 $$

Here, $exploit(T)$ denote the total number of "exploit" rounds performed in the first $T$ pulls. Given that expectation is defined as "the weighted sum of the outcome values, where the weights correspond to the probabilities of realizing that value",

(Q1) how exactly mathematically we define $\mathbb{E}[exploit(T)]$?

In second video (at 24:44), instructor has said that $\mathbb{E}[exploit(T)]$ is the number of exploit steps.

(Q2) Then how it equals "weighted sum of outcome values"?

(note that instructor assumes that the pulling of arm may give reward which correspond to outcome value of 1 and may not give reward which correspond to ourcome value of 0)

Also in slide 27, for GLIE-ifying $\epsilon_T$-first strategy, he selects $\epsilon_T=\frac{1}{\sqrt{T}}$. Then, the instructor counts $\sqrt{T}$ exploratory pulls and $T-\sqrt{T}$ exploitory pulls. Then to show that this satisfies condition C2, instructor states $$\mathbb{E}[exploit(T)]\geq \frac{T-\sqrt{T}}{T}$$.

Here, $\frac{T-\sqrt{T}}{T}$ is a fraction of exploitory pulls.

(Q3) So, by above equation does the instructor mean, number of exploitory pulls is greater than equal to fraction of number of exploitory pulls?

(Q4) How can we put 2nd equation in first equation and still prove limit in first equation still holds, that is, how following is the case:


I guess I am missing some basic concept of expectation here.


For (Q1) we mathematically define $\mathbb{E}[exploit(T)]$ as: $$\mathbb{E}[exploit(T)] = \sum_{t=1}^T (1-\epsilon_t)$$ where $\epsilon_t$ is the exploration probability at round $t$. The equation is basically telling us the expected number of times you pull a greedy arm over the time horizon $T$.

A more useful metric would be: $$\mathbb{E}[explore(T)] = \sum_{t=1}^T \epsilon_t$$

It os obvious that:

$$\mathbb{E}[explore(T)] + \mathbb{E}[exploit(T)] = T$$

First, I would like to gloss over the idea why this formulation produces sublinear regret. Although there are additional assumptions that have clearly not been mentioned in the lecture, I will say it here. There is a paradigm of a 'consistent' algorithm in online learning, which in simple terms mean that the actual best arm will be identified eventually as $T \to \infty$ and by the design of your algorithm, you will be pulling this arm greedily (or with a high probability) after some time giving you a regret better than linear regret.

Now in this case, if you assume the algorithm is 'consistent' it is clear that the number of exploration steps (which is decided by exploration probability) at each step will slowly have a reduced growth as compared to the linear case i.e you are now slowly reducing exploration as your 'consistent' algorithm gurantees you have with high probability identified the best arm. From this definition/intuition given above it is clear that this means that $\mathbb{E}[explore(T)]$ should grow at a slower rate while $\mathbb{E}[exploit(T)]$ should grow at a faster rate with $T$.

From this inutitive idea rises that: $$\lim_{T\rightarrow\infty}\frac{\mathbb{E}[exploit(T)]}{T}=1 $$ or $$\lim_{T\rightarrow\infty}\frac{\mathbb{E}[explore(T)]}{T}=0 $$

For (Q2), it is not. It might be in expectation, but in general, it is not. I am unsure of the type of bandits used here so I will not do this calculation. In anyways, whenever sampling is involved, it means you have sampled a trajectory or a particular instance of a joint probability distribution and its expectation can never be equal to one sample (we need $\infty$ samples).(Although I am not clear on this one, the slides are not very clear to me).

For (Q3) Yes. The instructor states an inequality which I could not reproduce (I tried to do it, but it reverses the inequality sign of the instructor, you can try it yourself using the below set of equations and using the fact that $\epsilon_T \leq \epsilon_t, \quad \forall T \geq t$). Now consider the following set of equations: $$\mathbb{E}[explore(T)] = \sum_{t=1}^T \epsilon_t$$

(a good approximate summation can be found using integrals like this) $$\mathbb{E}[explore(T)] \approx k \sqrt T$$

where $k$ is a constant.

$$-\mathbb{E}[explore(T)] \approx -k \sqrt T$$

$$T-\mathbb{E}[explore(T)] \approx T - k \sqrt T$$

$$\frac{\mathbb{E}[exploit(T)]}{T} \approx 1-k \frac{1}{\sqrt T}$$

which answers your (Q4) that: $$\lim_{T \to \infty} \frac{\mathbb{E}[exploit(T)]}{T} \approx \lim_{T \to \infty} 1-k \frac{1}{\sqrt T} = 1$$

  • $\begingroup$ Why the downvote? Did I make some mistake? $\endgroup$ – DuttaA Feb 21 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.