Reinforcement Learning - Lec3

Value-Based Algorithm - MC & TD

Reinforcement Learning
RL / NTU / CS294

前兩講 focus 在 policy-based 的 RL 演算法，直接 learn 一組參數去 parametrize policy。而後續兩講則會 focus 在 value-based 的方法，想法是算出 $V^\pi(s), Q^\pi(s,a)$ (同樣可以 approximately parametrized by $\theta$)，而所對應的 policy 則是去選擇 Given $s$，好度最高的 action $a$ (w/ appropriate exploration)。

Monte-Carlo Learning

回顧 Lec1，$V^\pi(s)$ 的定義是 expected return from state $s$， Monte-Carlo 的想法是直接 simulate 一個 trajectory from state $s$，然後去 reward 是多少， Value function 每一個 episode 更新一次。

\[ V(s_t) \leftarrow V(s_t) + \alpha(r(\tau) - V(s_t)) \]
  • Variance is high
  • Unbiased estimate

Temporal Difference Learning

Use bootstrapping to estimate final reward by $r(s,a) + V(s \scriptscriptstyle t+1 \textstyle)$，每走一步Value function 都會更新

\[ V(s_t) \leftarrow V(s_t) + \alpha(\underbrace{r(s,a) + \gamma V(s_{t+1})}_{\text{estimated} \; r(\tau)} - V(s_t)) \]
  • Variance is low
  • Biased estimate
  • Efficient (and even suitable for non-episodic game)

Remark:

  • 如此的迭代，又稱為 value iteration (如果過程中有 explicitly 表示出 policy ，又叫做 policy iteration)

  • 如前所述，這裡的 policy 是根據 $V(s \scriptscriptstyle t+1 \textstyle)$ 或 $Q(s,a)$ 決定 (直接 greedily 選 argmax)

  • 在 training 時，會希望增加 對 env. 的 exploration

    • $\epsilon$-greedy: 加上一個$\epsilon$ 的機率選擇其他非 argmax 的 action
    • Boltzmann exploration: follow $\exp(Q(s,a))$，並可用 temperature $T$ (a hyperparameter) 調整 exploration/exploition 的比重

  • 用 $V$ 做 criteria 的話，需要先知道 MDP 的 transition (但通常我們不知道)，\
    所以一般來說是利用 $Q^\pi(s,a)$ 當成 criteria，也是眾所周知的 Q-learning (Q-value iteration)

\[ Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha (r(s_t,a_t) + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)) \]
  • 一般在 $|\mathcal{S}|$, $|\mathcal{A}|$ 不小的情況下，會用 function family (parameterized by $\phi$) 去表示 $Q(s,a)$，而如何找到 $\phi$ 則是一個 regression problem
\[ \phi \leftarrow \arg \min_\phi \sum_n \sum_t ||Q_\phi(s^n_t,a^n_t) - y^n_t|| \]

Note: $\alpha$ 表示 value 隨新 data 更新的敏感度

Convergence to optimal policy (tabular case)

條件:

  • MDP is known
  • $|\mathcal{S}|, |\mathcal{A}|$ is small

Remark

所對應的 optimal value function 為下列 equation (先不管 $\alpha$)

\[ \begin{aligned} V_{\ast}(s) &= \max_\pi V_\pi(s) = \max_a Q_{\ast}(s,a)\\ Q_{\ast}(s,a) &= \max_\pi Q_\pi(s,a) = r(s,a) + \sum_{s^\prime} \mathbb{P}[s^\prime|a,s] V_{\ast}(s) \end{aligned} \]

  • 由上方 equation 可知 $Q_\ast$ 是上述 TD learning iteration operator $\mathcal{B}$ 的 fixed point (前提是知道 $\mathbb{P}[s^\prime|s,a]$)，$Q_\ast = \mathcal{B} Q_\ast$

  • $\mathcal{B}$ is a contraction, $||\mathcal{B}Q - \mathcal{B} \bar{Q}||_{\infty} \leq \gamma ||Q - \bar{Q}||_{\infty}$

由 Contraction Mapping Theorem 可知，$Q(s,a)$ 會以$\gamma$ 的 rate converge 到 $Q_\ast$

Non-convergence to optimal policy (approx. $Q_\phi(s,a)$ case)

現在我們把一個條件放寬，假設 $|\mathcal{S}|$, $|\mathcal{A}|$ 大到無法以 table 儲存，只能以一個 function family 去表示 $Q(s,a)$

在做 regression 找當前 iteration 最好的 $\phi$ 時，其實引進了一個 projection operator $\Pi$
(project on function family, with l2-norm)

可以證明 $\Pi$ 也是一個 contraction (w.r.t l2-norm)，但 $\mathcal{B}$ 卻是 contraction w.r.t $\infty$-norm
所以 $\mathcal{B}\Pi$ 並不是 contraction，也就不保證會收斂。

Remark: 有人可能會想說，那這樣不如就把 regression 改成 w.r.t $\infty$-norm 的 optimization 問題，但這樣的 optimization 是 intractable 的 (belong to NPC)

 
comments powered by Disqus