1
$\begingroup$

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:

$$\lim_{T=\rightarrow\infty}\frac{\frac{T-\sqrt{T}}{T}}{T}=1$$

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

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.