Reinforcement Learning - TD

Model-Free Incremental RL Algorithms（TD 是个算法大类）

在 Model-Free 的情况下，用 Experience 求解 Bellman Expectation Equation

所以 TD 的思想与 Stochastic Gradient Descent (SGD) 非常相近，算是某种 Stochastic Approximation Algorithm

另外，思想相近的算法还有 Newton's Method

 

 

 

1. TD(0)

TD Learning of State Value，是最最最基本的用于 Policy Evaluation 的 TD 算法

• 只能估计 State Value of a Given Policy

• 不能估计 Action Value

• 不能搜索 Optimal Policy

 

 

1.1 Problem Formulation

• Given

  1. Policy $\pi$$\pi$

  2. Experience Samples generated by $\pi$$\pi$ in the form

     $$\{(s_t,r_{t+1},s_{t+1}){\}}_t=\{s_0,r_1,s_1,\cdots ,s_t,r_{t+1},s_{t+1},\cdots \}$$

• Task

  Estimate State Values $\{v_{\pi }(s){\}}_{s\in \mathcal{S}}$$\{v_{\pi}(s)\}_{s\in\mathcal{S}}$ under $\pi$$\pi$

  $$v_{\pi }(s_t)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]\mathrm{\forall }{s}_t$$

 

 

1.2 Algorithm

核心机制类似于 Stochastic Gradient Descent

where

• $s_t⟶$$s_t\longrightarrow$ The visited State at Time Step $t$$t$

• $v_t(s_t)⟶$$v_t(s_t) \longrightarrow$ Estimation of State Value $v_{\pi }(s_t)$$v_{\pi}(s_t)$

• ${\alpha }_t(s_t)⟶$$\alpha_t(s_t)\longrightarrow$ Learning Rate depending on $s_t$$s_t$ at Time Step $t$$t$ (a small positive number)

 

1.2.1 关于第一个公式

• TD Target

  $${\overline{v}}_t=r_{t+1}+\gamma v_t(s_{t+1})$$

  where

  • $r_{t+1}⟶$$r_{t+1}\longrightarrow$ 当前通过 $s_t\to s_{t+1}$$s_t\to s_{t+1}$ 的 Transition 得到的 Reward

  • $\lambda ⟶$$\lambda\longrightarrow$ Discount Rate

  • $v_t(s_{t+1})⟶$$v_t(s_{t+1})\longrightarrow$ State Value Estimation of $s_{t+1}$$s_{t+1}$ at Time Step $t$$t$

    $v_t(s_{t+1})$$v_t(s_{t+1})$ 与 $v_{t+1}(s_t)$$v_{t+1}(s_t)$ 的意义是不同的！！！

    • 前者是在 Time Step $t$$t$，对下一个 Time Step $t+1$$t+1$ 可能抵达的 State $s_{t+1}$$s_{t+1}$ 进行的 State Value Estimation！

    • 后者是在下一个 Time Step $t+1$$t+1$，对当前 Time Step $t$$t$ 所 access 的 State $s_t$$s_t$ 进行的 State Value Estimation！

  TD Target ${\overline{v}}_t(s_t)$$\bar{v}_t(s_t)$ 是利用当前的 Experience Sample 对 $v_{\pi }(s_t)$$v_{\pi}(s_t)$ 的单步估计样本

  将其与 Bellman Expectation Equation 对比有助于理解其含义

  • State Value 定义式

    $$v_{\pi }(s_t)=\mathbb{E}[G_t|S_t=s_t]$$

    Discounted Return $G_t$$G_t$ 是 State Value $v_{\pi }(s_t)$$v_{\pi}(s_t)$ 的 Expectation

  • State Value 递推式

    $$v_{\pi }(s_t)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]$$

    这也是 BEE 的一种形式！（但不是 Matrix-Vector Form）（名字是我自己取的，这不重要）

  • TD Target

    $${\overline{v}}_t=r_{t+1}+\gamma v_t(s_{t+1})$$

    Discounted Return 公式展开是

    $$G_t=R_{t+1}+\gamma v_{\pi }(S_{t+1})$$

    公式结构的相似性说明，TD Target 类似是对 Discounted Return 的一次采样

    由于 Discounted Return 是 State Value 的 Expectation，所以 TD Target 成为与 $v_t(s_t)$$v_t(s_t)$ 作差的对象就非常合理咯

• TD Error

  $${\delta }_t=v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]$$

  • Intuition

    TD(0) 对 State Value Approximation 的 update 方式和 Newton's Method 非常像

    结合前文探讨的 TD Target 意义去看下面的这个改写公式，这个 TD Error 的写法是非常合理的

    $${\delta }_t=v_t(s_t)-{\overline{v}}_t$$

    It drives $v_t$$v_t$ towards ${\overline{v}}_t$$\bar{v}_t$

    $$\begin{array}{rl}{v}_{t+1}(s_t)& =v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-{\overline{v}}_t]\\ [v_{t+1}(s_t)-{\overline{v}}_t]& =[v_t(s_t)-{\overline{v}}_t]-{\alpha }_t(s_t)[v_t(s_t)-{\overline{v}}_t]\\ [v_{t+1}(s_t)-{\overline{v}}_t]& =[1-{\alpha }_t(s_t)][v_t(s_t)-{\overline{v}}_t]\end{array}$$

    由于 ${\alpha }_t(s_t)$$\alpha_t(s_t)$ 是一个 small positive number，所以有

    $$\begin{array}{c}0<1-{\alpha }_t(s_t)<1\end{array}$$

    所以

    $$|v_{t+1}(s_t)-{\overline{v}}_t|=[1-{\alpha }_t(s_t)]|v_t(s_t)-{\overline{v}}_t|$$

    且

    $$|v_{t+1}(s_t)-{\overline{v}}_t|\le |v_t(s_t)-{\overline{v}}_t|$$

    所以每次 Time Step 更新，$v_t(s_t)$$v_t(s_t)$ 一定会离 ${\overline{v}}_t$$\bar{v}_t$ 更近！

  • A Measure of the Deficiency between $v_t$$v_t$ and $v_{\pi }$$v_{\pi}$

    假设此时 $v_t=v_{\pi }$$v_t = v_{\pi}$，则

    $$\begin{array}{rl}{\delta }_{\pi ,t}& =v_{\pi }(s_t)-[r_{t+1}+\gamma v_{\pi }(s_{t+1})]\\ \mathbb{E}[{\delta }_{\pi ,t}|S_t=s_t]& =v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]\end{array}$$

    由于 TD Target 中提到的

    $$v_{\pi }(s_t)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]$$

    所以有

    $$\mathbb{E}[{\delta }_{\pi ,t}|S_t=s_t]=v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]=0$$

    即，当 TD Error $=0$$= 0$ 时，$v_t=v_{\pi }$$v_t = v_{\pi}$

 

1.2.2 关于第二个公式

对于所有在当前 Time Step 未被 access 的 State，其对应的 State Value 估计值不变

THAND GOD! 解释这个比上面那个烦人的公式方便多了...

 

 

1.3 Algorithm Derivation

这个算法的本质是用 Special Topics 里的 Robbins-Monro Algorithm 来解一个诡异的 BEE 的表达式

• BEE 的 State Value 递推式

  即 1.2.1 中提到的

  $$v_{\pi }(s_t)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]$$

• RM Problem Formulation

  $$\begin{array}{rl}g(v_{\pi }(s))& =v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]\\ & =0\end{array}$$

• RM Algorithm

  $$\begin{array}{rl}{v}_{k+1}(s_k)& =v_k(s_k)-{\alpha }_k\tilde{g}(v_k(s_k))\\ & =v_k(s_k)-{\alpha }_k\{v_k(s_k)-[r_k+\gamma v_{\pi }(s_k^{\prime })]\}\end{array}$$

  where $s_k$$s_k$ is the current state at Step $k$$k$, $s_k^{\prime }$$s_k'$ is the next state transitioned to after an action

  做如下两个修改，以适应 RL 语境

  • $\{(s_k,r_k,s_k^{\prime })\}⟶\{(s_t,r_{t+1},s_{t+1})\}$$\{(s_k, r_k, s_k')\} \longrightarrow \{(s_t, r_{t+1}, s_{t+1})\}$

    • 前者为 RM Algorithm 用到的一组样本，运算过程中需要不断采样，而它们都是独立采样的，有 independent & identically distributed 这一假设

    • 但是显然做 RL 的时候你肯定没那个心情去一组一组采，TD 依赖的是 Experience Samples (see 1.1) ("Trajectory")，而只有后者的形式才能表示一条 Trajectory

  • $v_{\pi }(s_k^{\prime })⟶v_{\pi }(s_{t+1})⟶v_k(s_{t+1})$$v_{\pi}(s_k') \longrightarrow v_{\pi}(s_{t+1}) \longrightarrow v_k(s_{t+1})$

    我们不可能预先知道 $v_{\pi }$$v_{\pi}$，所以只能用 $v_k$$v_k$，即其 Estimation 来代替

    这种替换仍然能确保 $v_k$$v_k$ 收敛

  最后变成

  $$v_{k+1}(s_t)=v_k(s_t)-{\alpha }_k\{v_k(s_t)-[r_{t+1}+\gamma v_k(s_{t+1})]\}$$

  然后，由于

  • $k$$k$ 和 $t$$t$ 实际上是同一个东西

  • ${\alpha }_t$$\alpha_t$ 在这个部分描述的算法中 depends on $s_t$$s_t$

  所以...Voila~

  $$v_{t+1}(s_t)=v_t(s_t)-{\alpha }_t(s_t)\{v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]\}$$

 

 

1.4 Convergence

• Theorem

  By the algorithm introduced in the above sections:

  Given Policy $\pi$$\pi$, if $\sum _t{\alpha }_t(s)=\mathrm{\infty }$$\sum_t\alpha_t(s) = \infin$ and $\sum _t{\alpha }_t^2(s)<\mathrm{\infty }$$\sum_t\alpha_t^2(s)<\infin$ for all $s\in \mathcal{S}$$s\in\mathcal{S}$

  Then, it is almost for sure that $v_t(s)\to v_{\pi }(s)$$v_t(s)\to v_{\pi}(s)$ as $t\to \mathrm{\infty }$$t\to\infin$ for all $s\in \mathcal{S}$$s\in\mathcal{S}$

• 关于 Learning Rate

  实操中 ${\alpha }_t(s_t)$$\alpha_t(s_t)$ 一般是一个 small constant（哪怕这会导致不满足 $\sum _t{\alpha }_t^2(s)<\mathrm{\infty }$$\sum_t\alpha_t^2(s)<\infin$）

  因为如果放任 ${\alpha }_t(s_t)$$\alpha_t(s_t)$ 越来越小，到很久很久以后 Experience Samples 就会因为 Learning Rate 过小而失去作用

 

 

 

2. Sarsa Algorithms

TD Learning of Action Values，功能为 Policy Evaluation

• 可以估计 Action Value

• 可以搜索 Optimal Policy

  因为它终于开始涉及 Action 了，能评估不同 Action 的效果（求 Action Value），就能设法用 $ϵ$$\epsilon$-Greedy 的方式去选出合适的 Action 来更新 Policy

 

 

2.1 Problem Formulation

• Given

  1. Policy $\pi$$\pi$

  2. Experience Samples generated by $\pi$$\pi$ in the form

     $$\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}){\}}_t=\{s_0,a_0,r_1,s_1,a_1,\cdots ,s_t,a_t,r_{t+1},s_{t+1},a_{t+1},\cdots \}$$

     State, Action, Reward, State, Action = SARSA

• Task

  Estimate Action Values $\{q_{\pi }(s,a){\}}_{s\in \mathcal{S},a\in \mathcal{A}}$$\{q_{\pi}(s, a)\}_{s\in\mathcal{S}, a\in\mathcal{A}}$ under $\pi$$\pi$

 

 

2.2 Sarsa

相当于 Action Value 版本的 TD(0)

• Mathematical Objective

  a stochastic approximation algorithm solving

  $$q_{\pi }(s_t,a_t)=\mathbb{E}[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|S_t=s_t,A_t=a_t]\mathrm{\forall }{s}_t,a_t$$

  这是一种 BEE 用 Action Value 表达的写法

• Algorithm

  每次 Update Action Value 需要的 Experience 为一组 $\{s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\}$$\{ s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}\}$

  $$\begin{array}{c}\{\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\{q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]\}\\ q_{t+1}(s,a)& =q_t(s,a)\mathrm{\forall }(s,a)\ne (s_t,a_t)\end{array}\end{array}$$

  where

  • $s_t⟶$$s_t\longrightarrow$ The visited State at Time Step $t$$t$

  • $a_t⟶$$a_t \longrightarrow$ The selected Action at Time Step $t$$t$

  • $q_t(s_t,a_t)⟶$$q_t(s_t, a_t) \longrightarrow$ Estimation of Action Value $q_{\pi }(s_t,a_t)$$q_{\pi}(s_t, a_t)$

  • ${\alpha }_t(s_t)⟶$$\alpha_t(s_t)\longrightarrow$ Learning Rate depending on $s_t,a_t$$s_t, a_t$ at Time Step $t$$t$ (a small positive number)

• Pseudo-Code

  

 

 

2.3 Expected Sarsa

与一般版本的 Sarsa 的区别在于 TD Target 稍微变了一下

这样能将每组 Experience 涉及的 Random Variable 减少

• Matwhematical Objective

  a stochastic approximation algorithm solving

  $$q_{\pi }(s_t,a_t)=\mathbb{E}[R_{t+1}+\gamma \mathbb{E}[q_{\pi }(S_{t+1},A_{t+1})|S_{t+1}]|S_t=s_t,A_t=a_t]\mathrm{\forall }{s}_t,a_t$$

  这是也一种 BEE 用 Action Value 表达的写法

• Algorithm

  每次 Update Action Value 需要的 Experience 为一组 $\{s_t,a_t,r_{t+1},s_{t+1}\}$$\{ s_t, a_t, r_{t+1}, s_{t+1}\}$

  $$\begin{array}{c}\{\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\{q_t(s_t,a_t)-(r_{t+1}+\gamma \mathbb{E}[q_t(s_{t+1},A)])\}\\ q_{t+1}(s,a)& =q_t(s,a)\mathrm{\forall }(s,a)\ne (s_t,a_t)\end{array}\end{array}$$

• Notes

  1. Needs more computation

  2. 由于减少了涉及的 Random Variable，所以能 reduce estimation variances

 

 

2.4 n-Step Sarsa

这是个介于 2.2 的一般 Sarsa 和 Monte-Carlo 之间的算法，关键在 Action Value 的公式上

• Intuition

  Discounted Return $G_t$$G_t$ can be written in different form as

  $$\begin{array}{rl}\text{Sarsa}⟵G_t^{(1)}& =R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\\ G_t^{(2)}& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{q}_{\pi }(S_{t+2},A_{t+2})\\ & ⋮\\ \text{n-Step Sarsa}⟵G_t^{(2)}& =R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})\\ & ⋮\\ \text{Monte-Carlo}⟵G_t^{(\mathrm{\infty })}& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots \end{array}$$

  [ WARNING ]

  请千万记住，以上只是 written in different forms！

  $$G_t=G_t^{(1)}=G_t^{(2)}=G_t^{(n)}=G_t^{(\mathrm{\infty })}$$

  所有的 superscript 都只是用于表示 $G_t$$G_t$ 的分解程度

• Mathematical Objective

  • Sarsa

    It aims to solve

    $$\begin{array}{rl}{q}_{\pi }(s,a)& =\mathbb{E}[G_t^{(1)}|S_t=s,A_t=a]\\ & =\mathbb{E}[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|S_t=s,A_t=a]\end{array}$$

  • Monte-Carlo

    It aims to solve

    $$\begin{array}{rl}{q}_{\pi }(s,a)& =\mathbb{E}[G_t^{(\mathrm{\infty })}|S_t=s,A_t=a]\\ & =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots |S_t=s,A_t=a]\end{array}$$

  • n-Step Sarsa

    It aims to solve

    $$\begin{array}{rl}{q}_{\pi }(s,a)& =\mathbb{E}[G_t^{(n)}|S_t=s,A_t=a]\\ & =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})|S_t=s,A_t=a]\end{array}$$

    • n-Step Sarsa = Sarsa, when $n=1$$n = 1$

    • n-Step Sarsa = Monte-Carlo, when $n=\mathrm{\infty }$$n = \infin$

• Algorithm

  每次 Update Action Value 需要的 Experience 为一组 $\{s_t,a_t,r_{t+1},s_{t+1},a_{t+1},\cdots ,r_{t+n},s_{t+n},a_{t+n}\}$$\{ s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, \cdots, r_{t+n}, s_{t+n}, a_{t+n}\}$

  We need to wait until Time Step $n+1$$n+1$ to update Action Value of $(s_t,a_t)$$(s_t, a_t)$

  $$\begin{array}{c}\{\begin{array}{rl}{q}_{t+n+1}(s_t,a_t)& =q_{t+n}(s_t,a_t)-{\alpha }_{t+n}(s_t,a_t)\{q_{t+n}(s_t,a_t)-(r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^{n-1}{r}_{t+n+1}+{\gamma }^n{q}_{t+n}(s_{t+n+1},A_{t+n+1}))\}\\ q_{t+1}(s,a)& =q_t(s,a)\mathrm{\forall }(s,a)\ne (s_t,a_t)\end{array}\end{array}$$

• Notes

  Performance is a blend of Sarsa and Monte-Carlo

  • if n is large, then it has a large variance but a small bias

  • if n is small, then it has a large bias but a small variance

 

 

 

3. Q-Learning

TD Learning of Optimal Action Values

和 Sarsa 很像，但 TD Target 以及做 Policy Improvement 时所用方法的区别非常大

 

 

3.1 Algorithm

• Mathematical Objective

  It aims to solve

  $$q(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{a}{max}q(S_{t+1},a)|S_t=s,A_t=a]$$

  This is a BOE instead of BEE expressed in terms of Action Values!

  所以 Q-Learning 能直接 estimate (optimal policy 对应的) optimal action value

• Algorithm

  每次 Update Action Value 需要的 Experience 为一组 $\{s_t,a_t,r_{t+1},s_{t+1}\}$$\{ s_t, a_t, r_{t+1}, s_{t+1}\}$

  $$\begin{array}{c}\{\begin{array}{rl}{q}_{t+n+1}(s_t,a_t)& =q_{t+n}(s_t,a_t)-{\alpha }_{t+n}(s_t,a_t)\{q_{t+n}(s_t,a_t)-[r_{t+1}+\gamma \underset{\alpha \in \mathcal{A}}{max}{q}_t(s_{t+1},a)]\}\\ q_{t+1}(s,a)& =q_t(s,a)\mathrm{\forall }(s,a)\ne (s_t,a_t)\end{array}\end{array}$$

  不需要 $a_{t+1}$$a_{t+1}$ 的原因是，它应该是通过 $\underset{a\in \mathcal{A}}{max}$$\max_{a\in\mathcal{A}}$ 得到的

• Notes

  Q-Learning 有 On-Policy 和 Off-Policy 两种版本

 

 

3.2 On-Policy Ver. Pseudo-Code

 

 

3.3 Off-Policy Ver. Pseudo-Code

请注意，Off-Policy Learning 的算法在 Update Policy 时不需要考虑 Target Policy 的探索性，反正 Behavior Policy 能 handle 探索的问题

所以，Behavior Policy ${\pi }_b$$\pi_b$ 与 Target Policy ${\pi }_T$$\pi_T$ 的分离，导致在 Update Policy 的时候，可以舍弃 $ϵ$$\epsilon$-Greedy 而直接用 Greedy 的方式更新

 

 

 

[ Notes ] Universal Expression

• Algorithm

  

• Mathematical Objective

  

 

 

 

[ Notes ] On/Off-Policy Learning

Temporal-Difference Learning 的算法涉及 Generate Experience 和 Optimize Policy 两件事

• Behavior Policy is used to Generate Experience Samples

• Target Policy is constantly updated towards Optimal Policy

所谓 On-Policy 与 Off-Policy 的区别便在于这两种 Policy 是否一致

• On-Policy Learning $⟶$$\longrightarrow$ Behavior Policy $=$$=$ Target Policy

  Policy 先被用来 Generate Experience，然后 Optimize，这两个步骤不断循环

• Off-Policy Learning $⟶$$\longrightarrow$ Behavior Policy $\ne$$\not=$ Target Policy

  Policy A 专门用来 Generate Experience，用来 Optimize Policy B

比如 Sarsa 和 Monte-Carlo 都是 On-Policy，Q-Learning 一般是 Off-Policy 的，但也可以被 implement 成 On-Policy 的形式

 

 

 

Special Topics - Robbins-Monro

这个 RM Algorithm 是 Temporal Difference Method 的基础

 

1. Algorithm

一种用于 Stochastic Approximation 的算法

• Problem Formulation

  很多问题都能写成这种形式：find the Root $w$$w$ of equation $g$$g$ that satisfies

  $$g(w)=0$$

  解的时候有两种情况：

  1. Model-Based

     即已知 $g$$g$ 是什么，那么就会有各种 Numerical Method 任君挑选

  2. Model-Free

     即未知 $g$$g$ 是什么，那么就用 Robbins-Monro (RM) Algorithm 来解

• Algorithm

  $$w_{k+1}=w_k-a_k\tilde{g}(w_k,{\eta }_k)$$

  where

  • $w_k⟶k^{th}$$w_k \longrightarrow k^{th}$ estimation of root

  • $\times a_k⟶$$\times a_k\longrightarrow$ 某 Positive Coefficient

  • ${\eta }_k⟶$$\eta_k\longrightarrow$ 观测时的 Noise，不理解可见 3.1 的例子

  • $\tilde{g}(w_k,{\eta }_k)=g(w_k)+{\eta }_k⟶$$\tilde{g}(w_k,\eta_k) = g(w_k) + \eta_k \longrightarrow$ Noisy Observation

  还是那句话：没 Model 就得有 Data，没 Data 就得有 Model

• Example

  $$g(w)=\tanh (w-1)$$

  Assume parameters

  • $w_1=3$$w_1 = 3$

  • $a_k=1/k$$a_k = 1/k$

  • ${\eta }_k=0⟶$$\eta_k = 0 \longrightarrow$ 即假设没有 Noise，$\tilde{g}(w_k,{\eta }_k)=g(w_k)$$\tilde{g}(w_k,\eta_k)=g(w_k)$

  则 RM Algorithm 为

  $$w_{k+1}=w_k-a_{k}g(w_k)$$

  迭代效果如下图

  

  实际上无论初始值的正负如何，最后总是能迭代收敛到 True Root $w^{\ast }=1$$w^* = 1$

 

 

 

2. Convergence Theorem

In RM Algorithm, if

• $0<c_1\le {\mathbf{\nabla }}_{w}g(w)\le c_2$$0 < c_1 \leq \grad_wg(w) \leq c_2$

  即 $g$$g$ 的图像始终递增且梯度有界，这样能确保一定有 $g(w^{\ast })=0$$g(w^*)=0$

• $\sum _{k=1}^{\mathrm{\infty }}{a}_k=\mathrm{\infty }$$\sum_{k=1}^{\infin}a_k = \infin$ and $\sum _{k=1}^{\mathrm{\infty }}{a}_k^2<\mathrm{\infty }$$\sum_{k=1}^{\infin}a_k^2 < \infin$

  后者确保 "$a_k\to 0$$a_k\to 0$ as $k\to \mathrm{\infty }$$k\to \infin$"，前者确保 "$a_k$$a_k$ 不会收敛得太快"

• $\mathbb{E}[{\eta }_k|{\mathcal{H}}_k]=0$$\mathbb{E}[\eta_k|\mathcal{H}_k]=0$ and $\mathbb{E}[{\eta }_k^2|{\mathcal{H}}_k]<\mathrm{\infty }$$\mathbb{E}[\eta_k^2|\mathcal{H}_k]<\infin$ where ${\mathcal{H}}_k=\{w_k,w_{k-1},...\}$$\mathcal{H}_k = \{w_k,w_{k-1},...\}$

  前者表示 "${\eta }_k$$\eta_k$ 的 mean 为 0"，后者表示 "${\eta }_k$$\eta_k$ 有界"，noise 不一定非要是 Gaussian

then $w_k$$w_k$ converges with probability 1 (w.p.1) to the root $w^{\ast }$$w^*$ satisfying $g(w^{\ast })=0$$g(w^*)=0$

“with probability 1” 表示的是概率意义上的收敛，因为涉及随机变量采样

 

 

 

3. More Examples

走过路过，不要错过！Mean Estimation！

 

 

3.1 嗯...

Solve for $w$$w$ with Independent & Identically Distributed Samples $\{x\}$$\{x\}$ of $X$$X$

Reformulate the problem to

得到的 Samples $\{x\}$$\{x\}$ of $X$$X$ 相当于是 Noisy Observation

where the Noise is

那么 RM Algorithm Formulation 为

 

3.2 哦吼吼～

增加点难度～

Solve for $w$$w$ with Independent & Identically Distributed Samples $\{x\}$$\{x\}$ of $X$$X$

Reformulate the problem to

得到的 Samples $\{x\}$$\{x\}$ of $X$$X$ 相当于是 Noisy Observation

where the Noise is

那么 RM Algorithm Formulation 为

 

3.3 《 你 好 》

再加点佐料～

Solve for $w$$w$ with Independent & Identically Distributed Samples $\{x\}$$\{x\}$ of $X$$X$ and Samples $\{r\}$$\{r\}$ of $R$$R$

Reformulate the problem to

得到的 Samples $\{x\}$$\{x\}$ of $X$$X$ 相当于是 Noisy Observation

where the Noise is

那么 RM Algorithm Formulation 为