Z's learning note

Search

SearchSearch

rl_overview

Dec 14, 2020, 14 min read

Reinforcement learning (based on David Silver’s lecture and WPI CS 525/DS 595)

参考书籍

  • Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto

General concept

RL的假设及与modern control的联系与区别

  • 基本假设：服从马尔科夫链，当前状态只依赖于前一状态 在设计状态时，状态应包含所有能将系统以马尔科夫链形式表示的信息，例如仅用物体的距离作为状态不足以满足马尔科夫链的要求时，将其一阶导数速度也作为状态。此时作为输入的加速度直接控制速度

RL的基本元素

  • 问题：何时抽象？何时具象？

      • 控制理论：以具体的变量作为，如位置，速度，角度等
      • end-to-end的方法是将图像/pixel在通过神经网络抽象后作为一个state
    • 具象的Action可以是grid world中那样上下左右的移动 抽象的Action是state -> state‘的原因，只要能使得一个state转移至下一个state，就可以作为一个action。
    • : The function defines the dynamics of the MDP. 从一个状态到另一个状态条件转移的概率。当概率为1时，是deterministic world；当概率小于1时，是stochastic world。所谓强化学习的模型（model-base，model-free），就是是否已知/存在条件转移概率 与的区别：同一个action 可能以不同的概率获得不同的reward（Reinforcement learning, p49）。

  • 的定义: return following time t.

  • : value function. 当前状态的价值，在一个MDP过程中，越大越接近goal。

    • End state的value永远是0。在End state时，执行任何action的next state均为end state（action不执行，状态不转移），不产生reward。Value初始化的时候为0，，所以迭代后恒为0。

  • : value-action pair. 在给定状态下，如果采取action ，效果如何（同一个时，越大越好）。在这一步的action还没有选定，其后的action均根据policy选定。

  • ，，的关系：是根据某一policy执行了一系列action到达终点后，从后向前推到状态时实际测出的价值。是在理想场景下以最优policy到达终点后返回去得出处的价值。从Monte Carlo的角度，是多次的期望。从Bellman equation的角度，应为该状态下最大的，真实测量的结果就是执行对应action（以及其后一连串action）得到的。 在有模型时，和模型中条件转移的概率组合可以得到在下执行的期望的价值. 在无模型的情况下，必须在该得到每个action对应的，从贪心算法的角度，最大即最优。 Prediction：评估value。 Control：有模型时求，无模型时求

  • Bellman optimality equations:

  • Model: 状态间条件转移概率

  • constant step-size parameter (Sutton’s book, p120 & Equation 2.4)

Dynamic programming动态规划

  • discrete state and input: dynamic programming. continuous state and input: approximate dynamic programming

  • Policy iteration从应用的角度比较intuitive一些，因为每次都是基于一个policy，收敛出严格按照这个policy执行时每个state对应的value，从value得出Q值，进一步提升policy。每一次policy与前一次相比都有所提升。与之相比，value iteration中并不是每一次迭代后的value表格都有有意义的policy与之对应（未必获得提升？即必须要等到value表格收敛，才能得出一个可靠的policy，不能随时中止获得一个当前最佳的policy？TODO：有时间验证一下）

  • 但是value iteration从始至终只需要value的参与，从代码的角度，更intuitive。

Value iteration价值迭代

  • 核心：计算所有，在一个下不同action中最大的Q-value作为

    不断迭代直到收敛（相邻两次的变化小于阈值）

  • 需要在收敛后Extract optimal policy

Policy iteration策略迭代

  • 核心：计算某一policy下的value，利用value更新值从而更新policy，如此迭代

    Given policy , evaluate its for all states, loop: 　　 　　　　　　　　↳：状态s时根据policy应执行的action；：模型的条件转移概率；：Q值表 　　 until policy_improvement：找出值最大的对用于更新，直到收敛

Function approximation

Prediction

  • : parameterized functional from with weight vector () weight的定义
  • : approximate value of state , with the vector of feature weights. Function : linear, decision tree, neural network, etc.
  • , is the distribution of , 　　　　 Eq.
  • SGD (Stochastic gradient-descent, Sutton’s book p201) 　　　　 Eq. Value Approx. is given by 将替换为对的测量。当时即为无偏估计。实际应用中用适当的测量方式替换，如
    • 是怎么来的？有存在，所以是否有这个其实都可以替换掉

Control

疑问

  • Function approximation算不算model based？应该不算

Monte Carlo & Temporal difference

Greedy

UCB (upper-confidence-bound) action selection

  • ：到第步（时刻） ：在此之前被执行过多少次 ：在多大程度上执行eploration

-greedy

GLIE

  • Greedy in the limit with infinite exploration, e.g., -greedy with 0
  • Review David Silver’s slides!

MC (-step TD)

MC prediction (first visit)

  • 核心：用于估计在对应policy下每个state的value

  • 通过多次采样，用的平均（(即）去逼近真实的值（对比）。G的定义见上文。

    初始化return_sum[s]，return_count[s]，V loop n episodes： 　　Generate an episode following policy : 　　 　　对于对，倒序访问 　　　　 　　　　如果在这个episode第一次(first visit)出现 　　　　　　将添加到访问记录 　　　　　　return_count[s]+=1#在n个episode中出现了几次 　　　　　　return_sum[s]+=G #其此时的g值 　　　　　　Ｖ[s]=return_sum[s]=return_sum[s]/return_count[s] 当所有episode结束时，V[s]即为此policy 的value function的近似。

MC control (on-policy, first visit)

  • 核心：

    初始化return_sum[s]，return_count[s]，Q loop n episodes： 　　Generate an episode by using current -table，同时引入-greedy添加访问的随机性（同一state中Q值最高的有最大可能作为policy），生成: 　　 　　对于对，倒序访问 　　if 在这个episode中第一次出现 　　　　return_count[s][a]+=1 　　　　return_sum[s][a]+=G 　　　　Q[s][a]=return_sum[s][a]/return_count[s][a] 当所有episode结束时，Q[s][s]即为此系统的近似Q-table，从中可以得到现阶段最优策略。

Temporal difference

One-step TD

TD(0) for estimating
  • 核心： 每次向可能正确的方向前进一小步
    • TD error:
  • No -value is involved, evaluation value function only, need model to find the optimal policy.
Sarsa (on-policy TD control, model-free)

  • 核心： 　　　　　　　　　　　　　　　　　　　　　↳current policy is used here. 利用估计出的-table 　- TD error: 　- TD target: 　- 当选择action是依据policy时，则有

  • 超参：

    初始化Q（start with any -table） loop n episodes： 　　 　　利用-table根据现在所处state选出第一个action：a = -greedy(Q, s, ) 　　reset环境 　　while not done： 　　　　s’, r = env.step(a) # selcet an action “a” using -greedy & Q, take this step 　　　　a’ = -greedy(Q, s, ) # 根据现有Q-table选下一步所要采取的action 　　　　 = r + Q[s’][a’] 　　　　 = (-Q[s][a]) 　　　　Q[s][a] += 　　　　 　　　　s=s’, a=a’ return Q

Q-learning (off-policy TD control, model-free)
  • 核心： ↳current policy is not used here. 直接选取了状态中Q值最高的action

初始化Q（start with any -table） loop n episodes： 　　reset环境 　　while not done： 　　　　a = -greedy(Q, s, ) 　　　　s’, r = env.step(a) # selcet an action “a” using -greedy & Q, take this step 　　　　 = r + max(Q[s’][a’]) 　　　　 = (-Q[s][a]) 　　　　Q[s][a] += 　　　　 　　　　s=s’ return Q

Comparison between different TD(0), SARSA, and Q-learning
NameEquationNote
TD(0)value evaluation, apply model to get Q
SARSAon-policy
Q-learningoff-policy

-step TD

-step TD prediction
  • 实际情况中，只有在执行从到这一步时，才能获得从到的reward
  • 表示在进行到步时状态的value。
  • 类似与泰勒展开后忽略高阶项，-step TD忽略了之后的项并用替代
  • 具体意义：
    • 从时刻（令此时所处状态为）起记录其后的步（每一步的reward）
    • 当执行第步后，即可做出估计：在抵达时，处的G值可近似为 （前步为以某种依据选取action后获得的reward的影响，步之后的用出的value近似）。
    • 由此可以更新处的value：
-step Sarsa
  • Extend one-step to -step
  • Replace the in TD prediction by
-step off-policy learning (off-policy -step Sarsa)
  • 优化policy的同时增加另外一组policy 。用于exploitation（如greedy），用于eploration（如-greedy）。计算Q时采用在policy 采用的结果（off-policy）。
  • , importance sampling ratio 探索过程中利用当前最优结果的比例？大概的理解：

Comparison

on-policyoff-policy
MCMC control
TDSARSA

更新Q值时，之后的Value即为根据当前policy下一步采取action所对应的Q值		Q-learning

更新Q值时，之后的Value为当前state所对应的所有Q值中最大的（不一定是根据policy选取action对应的Q值）

TD()

  • Eligibility trace: vector ，与维度相同，是每个weight分量对应的梯度的表象。 (let )

    zvalue

    意义：距离现在状态(S_t)越远的步骤，其的梯度对现在影响越小

  • TD error: 与之前定义的TD error类似，

  • 将TD的误差（新的估计与前次估计的差）通过梯度（时间越久远的梯度作用越小）叠加到现在的weight上完成更新。更新weight的同时v由function approximation也得到了更新

  • 实现（还没自己实现过）：

    loop for each episode： 　　初始化 　　 　　while not done： 　　　　Choose 　　　　Take action , observe , 　　　　 　　　　 　　　　 　　　　

Policy gradient methods

  • : policy parameter vector Policy update: e.g.:

    • function : parameterized numerical preferences。若假设是线性关系，可定义为，其中是pair的feature vector
    • policy的选取：

  • Comparison with value approximation

    value approximationpolicy approximation

    Eq. Value Approx.

  • 。的定义参考Eq.
    意义：综合了状态出现的概率，Q值及policy的梯度

Actor-critic

  • One-step actor-critic

  • Comparison with TD()

    Actor-criticTD()
    > loop for each episode：> loop for each episode：
    >　　初始化>　　初始化
    >　　>　　
    >　　
    >　　
    >　　while not done：>　　while not done：
    >　　　　Choose >　　　　Choose
    >　　　　Take action , observe , >　　　　Take action , observe ,
    >　　　　>　　　　
    >　　　　>　　　　
    >　　　　
    >　　　　>　　　　
    >　　　　
    >　　　　
    >　　　　>　　　　

TODO

Backlinks