强化学习

强化学习 阅读笔记

RL

agent interact with environment over time

感知 sensation / 决策 action / 目标 goal

四要素

与监督学习区别: 监督学习, 通过对于训练集归纳, 预测未见数据. 相当于给了每种棋局的最优解法, 但是缺少学习体和机制的交互过程. 实际问题可用于训练的标注数据很少, 需要学习体不断实践拿反馈, 生成训练数据, 自学成才.

与无监督学习区别: RL的目标是最大化奖赏, 无监督学习旨在发现背后的结构. 当然理解世界运作机制有助于最大化奖赏, 不过这是个更难的问题.

白盒还是黑盒学习?

MAB / multi-armed bandit / 多臂赌博机

多个赌博机, 每个以一定概率分布输出奖励. 求一个策略, 找到最好的机位, 及最大化收益.

bandit: 强盗, 赌博等于抢钱

现实例子: 买哪家股票, 决定点哪家外卖, 活分给谁干, 等等.

策略

单臂赌博机? one-armed bandit 单摇杆的赌博机, 只要玩下去, 没有选择的机会, 这里多臂还是多台机器没有区别, 主要是为了引入选择性. 这里每个赌博机的奖励分布函数未知. 知道了, 相当于开了上帝视角, 拿着期望最大的使劲薅即可.

上面讨论只考虑了奖励函数是固定的 (stationary). 如奖励概率函数时间相关缓慢变化的 (non-stationary), 则平均收益做滑窗或者指数平均, 而不采用初始至今的算数平均即可.

此外, 实际问题中, 是有状态的, 受行为及奖励结果动态变化的, 比如基于当前机子累计收益给奖励 (庄家永不输), 及”十抽保SSR”之类.

EE / Explore and Exploit

探索与利用的困境: 应该面试到第几个人录用, 应该和第几个女友结婚?

如果人生是无限的, 或者可以随时重来, 那么多探索, 可以发现全部的可能性; 可惜在有限的一次生命中, 只能看一步走一步.

年轻时候机会成本低, 多探索; 年长后多利用所谓人生经验, 吃老本.

Gittins-index

…

MDP / Markov Decision Process

马尔可夫假设回顾: 下一步只和当前相关, 和过去无关, 极大的简化了问题形式. 一般不成立. 比如和对象一起交往, 当前没做好, 可能连带起历史恩怨翻旧账, 直接火力全开吵起来.

MDP定义

这里当作离散问题表述, 即S/A/R可枚举, 实际连续问题也离散化去近似, 每一步的行为导致奖励以及状态的变化

MAB例子: 每个机子带了状态, 决定了当前奖励概率

下棋例子: S完全确定的, R是否获胜, A落子, d=对手决策

R很难制订, 和目标相关

R只告诉目标, 不透露方法: 例如下棋, 不能以吃子/损子作为R, 只在死棋状态时给出+1赢/-1输信号 把R当作KPI, 怎么实现得自己琢磨. 好的R能帮助快速学习达到目的.

G目标函数 / 收益: 从当前步往后看, 最大化未来的期望累计奖励

G(t) = R(t+1) + l * G(t+1)
G(t) = sum(l**(i-t) * R(i) for i in t+1 ... T)

陶渊明 / 归去来兮辞: 悟已往之不谏, 知来者之可追.

李白: 弃我去者昨日之日不可留, 乱我心者今日之日多烦忧.

二仙桥大爷: 向前看

Bellman方程: 当前价值函数和下一步价值函数的关系

v(s,p) = sum(p(a,s) * q(s,a,p) for a in A)
q(s,a,p) = sum(d(s,s2,a,r)*(r+l*v(s2,p)) for s2 in S for r in R)

v/q两者是不用区别看待, 等效的, 都可以叫做价值函数. 价值函数是对于策略p的泛函, 即给定策略p, v是确定的可计算出来的.

策略的偏序关系: p1 >= p2 iff all(v(s,p1) >= v(s,p2) for s in S). 偏序定义: 不是任意两个策略是可比较的. 一定有存在(一个或一簇)最优策略.

MDP模型下的问题表述: 给定当前状态s, 求最优策略及对应最大价值

p(s) = argmax(v(s,p) for all possible p)
v(s) = max(v(s,p) for all possible p)

优化问题表述形式, 不过这里参数是函数族(p), 而不是确定的参数数值空间, 因为标准优化问题对于策略结构做了明确的结构假设

对于最大价值函数, 类似的有Bellman方程表示 (Bellman optimality equation)

v(s) = max(q(s,a) for a in A)
q(s,a) = sum(d(s,s2,a,r)*(r+l*v(s2)) for s2 in S for r in R)

表述了当前状态的最大价值和下一步每个状态最大价值的关系, 是可唯一求解的. 和上面的区别在于是否是对于策略函数p的泛函表示, 这里脱掉了p.

解出v(s), 自然知道了最优策略 (Q: WHY)

p(s) = argmax(q(s,a) for a in A)

到目前为止, “数学”层面的讨论结束了, 即存在性, 任何MDP问题一定存在最优玩法. 往下是”算学”的工作 (找到解): 求解Bellman方程.

最简单的办法, 穷举; 类比复仇者联盟终局之战, 穿越时空到每个可能性的平行宇宙, 找到当下最优的选择.

现实问题

  1. 世界运作的机制d, 对于学习者来说, 一般是未知的
  2. 维度灾难 (按照空间x状态x奖励空间的树展开), 计算不可行

DP / dynamic programming

条件: d已知, 以及d和p是确定性的

迭代步骤 (GPI / generalized policy iteration)

  1. 策略评估 / policy evaluation: 给定策略p, 评估v
  2. 策略更新 / policy improvement: 基于评估v, 更新p

有点类似啥?

策略评估: 给定策略p, 迭代的方式拟合v(s,p), 一定是收敛的, 数值计算过程

policy evaluation

def get_v(p):
  v = {s: rand() for s in S}  // 价值函数随机初始化 
  while True:
    e = 0  // 当前迭代步数值变化上界, 理解为v的F范数距离即可
    for s in S:
      new_v = sum(x(a,s2)*(sum(p(s,s2,a,r)*(r+u*v[s2])) for s2 in S for r in R) for a in A)
      e = max(e, abs(new_v-v[s]))
      v[s] = new_v  // 这里直接更新回原函数, 不用单独维护两个
    if e < E:  // 推出条件认为收敛了
      return v

找更优策略: p2 >= p1 iff all(v(s,p2) >= v(s,p1) for s in S)

等价于: p2 >= p1 iff all(q(s,p2(s),p1) >= v(s,p1) for s in S)

greedy policy / 贪心更新策略: p2(s) = argmax(q(s,a,p1) for a in A) 即只调整当前一步, 找当前最优的选项

policy iteration

def get_best_p():
  p = {s: random.choice(A)} // 初始策略随机初始化
  while True:
    v = get_v(p)
    is_stable = True  // 策略是否不更新了, 即收敛到最优解了
    for s in S:
      old_a = p[s]
      new_a = argmax(sum(d(s,s1,a,r)*(r+l*v[s2]) for s2 in S for r in R) for a in A)
      p[s] = new_a
      if old_a != new_a:
        is_stable = False
    if is_stable:
      return p

这里每一轮重新估计v, 实际上是不需要的, 因为拿到的最大v等效拿到了最优策略, 因此上面的迭代argmax换成max后, 即迭代算出最大v即可

value iteration

def get_max_v(p):
  v = {s: rand() for s in S} 
  while True:
    e = 0
    for s in S:
      new_v = max(x(a,s2)*(sum(p(s,s2,a,r)*(r+u*v[s2])) for s2 in S for r in R) for a in A)
      e = max(e, abs(new_v-v[s]))
      v[s] = new_v
    if e < E:
      return v

DP缺点: 每一轮遍历状态空间费时 for s in S 办法: 偷鸡, 每一轮只访问一部分状态做更新. 类比SGD, 正常优化步骤, 是看完一整轮数据后再更新, 但是SGD每轮BATCH直接更新.

DP算法针对问题大小是多项式时间复杂度的O(|S|*|A|), 尽管策略空间是|S|**|A|

这里DP是针对MDP问题形式的讨论, 广义算法上常提的DP, 即动态规划, 对于问题的要求:

MC / Monte Carlo

DP里面要求d已知, 且实际计算困难.

对于MC方法, 不要求知道d, 但是要求有中止态的, 假设最多T步结束.

大数定理, 反复多次观测, 最终观测均值一定收敛到期望

书读百遍, 其意自现

策略评估: 给定策略p, 通过反复的模拟采样, 利用观测平均价值去拟合v(s,p), 或者等价的q(s,a,p).

优势

  1. 对于每个状态可以完全独立做采样过程, 而不是像DP这样基于其他状态结果 (即bootstrap特性)
  2. 每轮采样计算和最终步长有关, 和状态维度无关, 显著降维
  3. 可以选择从指定开始的状态去模拟, 而不用计算所有状态的价值, 更加实用
  4. 每次都是整体跑完一轮, 对问题的马尔科夫性不敏感

EE in MC: 策略的随机性. 如果p是确定的, 则对于q(s,a,p)的估计缺少很多(s,a)的结果. 一种办法, 先乱走一步, 再遵循既定的策略 (Exploring Starts).

stats = defaultdict(list) // 观测记录, 可简化
q = {(s,a): 0 for s in S for a in A}  // 行动价值函数

def p(s): // 当前策略函数
  return argmax(q[s,a]) for a in A)

while True:  
  s = random.choice(S)  // 随机开局
  a = random.choice(A)  // 乱走一步
  ss, as, rs = simulate(s,a,p)  // 模拟一局, 得到每一步的状态/决策/奖励列表
  g = 0  // 从后向前计算价值
  for t in range(T, 0, -1):
    g = rs[t] + r*g
    // first visit: 只记录每个状态的第一次
    if (ss[t],as[t]) in list(zip(ss[:t],as[:t])):
      continue
    stats[(ss[t],as[t])].append(g)  // 对于当前(s,a)的价值观测
  q = {sa: avg(samples) for sa in stats}  // 到当前步拟合的结果

这里习得的是一个确定性的函数. 如果引入了EE, 如采用e贪心策略, 则整个过程可以去掉第一步的乱走. 伪码略.

on-policy VS off-policy: 生成样本数据的策略和优化的目标策略是否要求同一个, off-policy里面会有两个策略. 人是否能完全自学顿悟, 还是需要借助他人知识. 从定义来说, off-policy包含on-policy, 自然更为强大, 学下棋给不给棋谱; on-policy简单, 收敛更快. 对于上文e贪心策略而言, 属于on-policy, 收敛到一个仍然保留探索可能性的策略; 对于off-policy, 则有一个用于训练的策略, 以及输出一个可能没有探索的, 确定性的, “实战”策略.

first visit VS every visit: 观测序列里面是否允许包含当前预测态, every visit方式统计上来说结果有偏差, 但是更简单.

TD / Temporal Difference Learning

TODO MC和DP的组合

棋类游戏不败策略

game theory

博弈场景: p ~ d

Zermelo’s theorem: 在二人的有限交互进行游戏中, 如果双方皆拥有完全的资讯, 并且运气因素并不牵涉在游戏中, 那先行或后行者当中必有一方有必胜/必不败的策略

解决的强度

23年黑白棋被解决了(弱解)

国际象棋/围棋并没有被解决, 只是电脑的策略胜过了人类

HOME