GLIE

Greedy in the Limit with Infinite Exploration

• All state-action pairs are explored infinitely many times,

  $$\forall s,a\underset{t\to \infty }{\lim }{N}_t(s,a)=\infty$$

• The policy converges to a greedy policy,

  $$\underset{t\to \infty }{\lim }{\pi }_t(a\mid s)=\mathcal{I}\left(a=\arg \underset{a^{\prime }}{\max }{q}_t(s,a^{\prime })\right)$$

- For example, $\epsilon$-greedy with $\epsilon_k = \frac{1}{k}$ GLIE Model-free control converges to the optimal action-value function, $q_{t}\rightarrow q_{*}$.