Understand the intuition behind MDPs leading to Reinforcement Learning and the Q-learning algorithm.
Reinforcement Learning

Reinforcement Learning

I would like to give full credits to the respective authors as these are my personal python notebooks taken from deep learning courses from Andrew Ng, Data School and Udemy :) This is a simple python notebook hosted generously through Github Pages that is on my main personal notes repository on https://github.com/ritchieng/ritchieng.github.io. They are meant for my personal review but I have open-source my repository of personal notes as a lot of people found it useful.

Approaches to RL

MDP's Value Function

  • $$ U(s) = R(s) + γ \max_a \sum_{s'}T(s, a, s') U(s') $$
  • $$ π(s) = argmax_a \sum_{s'}T(s, a, s') \ U(s') $$

Q function

  • $$ Q(s, a) = R(s) + γ \sum_{s'}T(s, a, s') \max_{a'} Q(s', a') $$
    • Value for arriving in s
    • Leaving via a
    • Proceeding optimally thereafter

Defining MDP's Value Function as Q Functions

  • $$U(s) = \max_a \ Q(s, a)$$
  • $$π(s) = argmax_a \ Q(s, a)$$

Q-learning

  • Evaluating the Bellman equations from data.
    • We need to estimate Q from transitions .
      • s, a, r, s'
        • We are in a state, we take an action, we get the reward and we are in the next state.

Estimating Q from Transitions: Q-learning Equation

  • $$ \hat{Q}(s, a)\leftarrow_{\alpha_t} \ r + γ \ \max_{a'} \hat{Q}(s', a') $$
  • Intuition: imagine if we've an estimate of the Q function.
    • We will update by taking the state and action and moving a bit.
    • We have the reward and discount the maximum of the utility of the next state.
  • This represents the utility function.
    • $$r + γ \ \max_{a'} \hat{Q}(s', a')$$
  • This represents the utility of the next state.
    • $$\max_{a'} \hat{Q}(s', a')$$
  • $\alpha_t$ is the learning rate.
    • $ V \leftarrow_{\alpha_t} X $
    • $ V \leftarrow (1-\alpha_t)V + \alpha X $
      • When $\alpha = 0$, you would have no learning at all where your new value is your original value, V=V.
      • When $\alpha = 1$, you would have absolute learning where you totally forget your previous value, V leaving your new value V = X.

Convergence of Q-Learning Equation

  • $\hat{Q(s, a)}$ starts anywhere
  • $$ \hat{Q}(s, a)\leftarrow_{\alpha_t} \ r + γ \ \max_{a'} \hat{Q}(s', a') $$
  • Then $\hat{Q(s, a)} \rightarrow Q(s, a)$
    • The solution to Bellman's equation
  • But, this is true only if
    1. (s, a) is visited infinitely often.
    2. $\sum_t \alpha_t = ∞$ and $\sum_t \alpha^2_t < ∞$
    3. s' ~ T(s, a, s') and r ~ R(s)

Q-learning is a family of algorithms

  • How to initialize $\hat{Q}$?
  • How to decay $\alpha_t$?
  • How to choose actions?
    • $\epsilon$-greedy exploration
      • If GLIE (Greedy Limit + Infinite Exploration) with decayed $\epsilon$
      • $\hat{Q} \rightarrow Q$ and $\hat{π} \rightarrow π^*$
        • $\hat{Q} \rightarrow Q$ is learning
        • $\hat{π} \rightarrow π^*$ is using
      • We have to note that we face an exploration-exploitation dilemma here that is a fundamental tradeoff in reinforcement learning.

Further Readings

Tags: machine_learning