强化学习是介于监督学习与非监督学习之间的一种学习.这么说的原因是因为,强化学习所用的数据并没有标记,所以它不是监督学习.如果说它是非监督学习也不正确,因为它有所有的奖励函数对结果进行反馈,这也可以算是一种监督,但相比标记数据的监督要少的多.

比如训练AI学习下棋,我们不知道下在什么地方才是好棋,但是可以根据结果的胜负来做奖励或者惩罚,随着时间的推移,它会做的越来越好.就好比训练一只狗,当它做的好奖励它,做的不好的时候惩罚它,狗会学会做越来越多好的事.

马尔可夫决策过程 (MDP)

马尔可夫决策过程包含这样几个元素 (S, A, \{P_{sa}\}, γ, R), 其中:

  • S为状态集合.
  • A为动作集合.
  • P_{sa}为状态转移概率.
  • \gamma \in [0,1)为折扣因子.
  • R为奖励函数.

举个简单的例子,想象一下一个机器人生活在一个网格的世界里,阴影是障碍物.机器人想要到达右上角,使用+1作为奖励,并且机器人要避免到达-1的位置.

在这个例子中,机器人一共有11个可能的位置所以它有11个状态:
S = \{(1,1),(1,2)....\}

机器人可以向四个方向运动,所以它的动作集合为:
A = \{N,S,E,W\}

当我们命令机器人向前走的时候,由于噪声等原因,机器人有一定的概率没有向前走,而是像左或者右走:

假设机器人现在在(3,1)位置上,如果用状态转移概率来描述的话为:
P_{(3,1),N}((3,2)) = 0.8
P_{(3,1),N}((4,1)) = 0.1
P_{(3,1),N}((2,1)) = 0.1
P_{(3,1),N}((3,3)) = 0
\qquad \vdots

再来看一下奖励函数,为了让机器人以最快的方式到达目的,我们要收取机器人的燃油费:
R((4,3)) = +1
R((4,2)) = -1
R(s) = -0.02

在机器人开始运动的时候,首先我们会选择一个初始状态s_0,然后再选择一个动作a_0,随后你会的到一个新的状态s_1 \sim P_{s_0a_0},接下来再选择一个动作a_1,随后又得到一个新的状态s_2 \sim P_{s_1a_1}

我们把每个状态使用奖励函数,得到总的奖励:

R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+...

这里的\gamma是折扣因子,因为前面的动作会影响整个后面的动作,所以前面决策的正确与否影响更大,所以给与的奖励更多.

强化学习的目标就是让总奖励的期望最大化:
E[R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+...]

假设我们现在的状态为s,我们通过带入函数就可以的到下一步a的状态,a=\pi(s),那么我们把这个函数\pi称为策略函数.

value function

我们定义值函数:
V^\pi(s) = E[R(s_0)+\gamma R(s_1)+\gamma^2 R(s_2)+...| s_0 = s,\pi]

例如下面是对应\pi的值函数分布:

我们对值函数进行一下变形:
V^\pi(s) = E[R(s_0)+\gamma (R(s_1)+\gamma R(s_2)+...)| s_0 = s,\pi]

其中R(s_1)+\gamma R(s_2)+...相当于V^\pi(s'),所以值函数又可以写为:

V^\pi(s) = R(s)+\gamma \sum_{s'} P_{s\pi(s)}(s')V^\pi(s')

其中添加\sum_{s'} P_{s\pi(s)}(s')的原因是s'是个随机变量,所以需要计算一下概率.P_{s\pi(s)}(s')表示从ss'的概率.

这个方程叫做贝尔曼方程.

举个例子,假设现在小车在(3,1)位置,且\pi((3,1)) = N:

V^\pi((3,1)) = R((3,1))+\gamma [0.8V^\pi((3,2))+0.1V^\pi((4,1))+0.1V^\pi((2,1))]

我们定义最优值函数为:
V^*(s) = max_\pi V^\pi(s)

即:
V^*(s) = R(s) + max_a \sum_{s'} P_{s\pi(s)}(s')V^\pi(s')

由此我们可以得出最佳测量函数\pi^*(s)的定义:
\pi^*(s) = arg \; max_a \sum_{s'} P_{sa}(s')V^\pi(s')

值迭代算法

first-step,初始化:

V(s) = 0

例如上面机器人的例子,就是创建一个11个元素的数组.

second-step,循环每一个状态,计算每个状态的值,也就对11状态调用最优值函数:

V(s) := R(s) + max_a \sum_{s'} P_{s\pi(s)}(s')V^\pi(s')

当运行完算法之后,V(s)会收敛到V^*(s),下面是算法得到的V(s):

你已经知道该如何走了对么,每次只要向着更大的V(s)走就对了.这里有人可能会疑惑,在位置(3,1)看起来向N走更近一些啊,不要忘了机器人有一定几率走偏,那么它有可能走向-1,所以它采取了更为稳健的方式.

策略迭代算法

first-step,随机初始化策略函数\pi(),就像这样:

second-step,循环下面两步:
V := V^\pi
\pi(s) := arg \; max_a \sum_{s'} P_{sa}(s')V(s')

当运行完算法之后,\pi(s)会收敛到\pi^*(s)

估计P_{sa}

回顾一下MDP中的5个元素,(S, A, \{P_{sa}\}, γ, R),其中S, A, γ, R,我们都可以得到,但是P_{sa}通常情况我们是事先不知道的.所以需要通过数据估计P_{sa}.

posted @ 2018-09-05 17:33:12
评论加载中...

发表评论