1-基本概念

第1课-基本概念（State,action,policy等）_哔哩哔哩_bilibili

---

Grid world example

本课程和textbook自始至终以grid world举例，因为这非常容易理解也很直观。在网格世界中，可以想象有一个机器人（称为agent）每次只能移动一格，它的目的是在初始位置（图1中绿色）以“最好”的方式到达终点（图1中黄色），中途会遇到一些障碍物（图1中红色）而不能进入.

事实上这个问题很直观地就可以理解，但是实际上仍然可以十分复杂，例如：

1. 目标是只需找到一个确定位置到达Target的最佳方式还是任意给定位置都可以找到最佳方式？
2. 目标中的“最好”如何理解？最短的路径？不要撞墙？还是不要撞到障碍物？
3. 障碍物是绝对不能进入还是可以但是进入了会有惩罚？惩罚多少？如何施加？
4. 当agent清晰周围环境时，规划路径实际上很容易，但是当不知晓时如何解决？

Basic Concepts – under a grid world example

State and action

• State (状态): 描述agent在环境中的状态，在grid world中指的是位置(location)，记为 $s_i$。
• State Space (状态空间): state的集合，记为 $S=\{s_i{\}}_{i=1}^n$。
• Action (动作): 表示agent在某状态下采取的行动，记为 $a_i$ (例如图2)。
• Action space (动作空间): action的集合，其依赖于所处状态，因为不同状态下能做出的行动可能不同。
• Action Space of state (特定状态的动作空间): 某状态下对应的action space，记为 $A(s_j)=\{a_i{\}}_{i=1}^k$。

State transition

State Transition (状态转移): 某一个状态采取了行动转变成另一个状态，例如记为 $s_1\stackrel{a_2}{\to }{s}_2$。其定义了agent与environment交互的行为，可以用表格(tabular)的形式表现出来，但只能表现确定性的情况(deterministic case)。

	$a_1$ (upward)	$a_2$ (rightward)	$a_3$ (downward)	$a_4$ (leftward)	$a_5$ (still)
$s_1$	$s_1$	$s_2$	$s_4$	$s_1$	$s_1$
…	…	…	…	…	…
$s_9$	$s_6$	$s_9$	$s_9$	$s_8$	$s_9$

State transition probability (状态转移概率): 使用概率表示state transition，如 $P(s_2|s_1,a_2)=0.9$ 表示在state $s_1$ 时采取action $a_2$ 变成state $s_2$ 的概率。这样就可以将deterministic case变为stochastic case。

Policy and reward

Policy (策略): 告诉agent在某状态时应该采取什么行动，记为 $\pi$，在数学上实际上就是条件概率。例如在state $s_1$ 时可以采用3种action，记为 $\pi (a_1|s_1)=0,\pi (a_2|s_1)=1,\pi (a_3|s_1)=0$，那么说明一定会采取action $a_2$。同一个state下不同action的 $\pi$ 的和为1。Policy也可以使用表格(tabular)形式表达（如表），称为tabular representation。

	$a_1$ (upward)	$a_2$ (rightward)	$a_3$ (downward)	$a_4$ (leftward)	$a_5$ (still)
$s_1$	0.2	0.1	0	0.5	0.2
…	…	…	…	…	…
$s_9$	1	0	0	0	0

Reward (奖励): 一个实数标量，一般当为正时表示对模型的奖励(encouragement)，为负时表示对模型的惩罚(punishment)。

1. 其实际上是人与机器交互的手段(human-machine interface)，用以引导使agent的表现符合预期。
2. 对于较复杂的任务，reward的设计也需要很好的前置专家知识，但是较于其他需要更多专业知识的方法已经较为简单
3. Reward也可以使用表格(tabular)形式表达（如表3所示）。同时，reward也可以用条件概率以随机化，例如 $P(r=-1|s_1,a_1)=0.9$ 表示在state $s_1$ 时采取action $a_1$ 产生的reward为 $r=-1$ 的概率为0.9。
4. 一个好的policy并不是每一步都选择当前最大的reward，因为immediate reward最大并不意味着最后的total reward最大。
5. Reward取决于当前的状态和动作，并不取决于下一步的状态，如原地不动和”撞墙”下一步的状态相同，但是reward一般不同。

	$a_1$ (upward)	$a_2$ (rightward)	$a_3$ (downward)	$a_4$ (leftward)	$a_5$ (still)
$s_1$	$r_{bounary}$	0	0	$r_{bounary}$	0
…	…	…	…	…	…
$s_9$	$r_{forbidden}$	$r_{bounary}$	$r_{bounary}$	0	$r_{target}$

Trajectories, returns, and episodes

Trajectory (轨迹): 是一个 state - action - reward chain，例如

$$s_1\underset{r=0}{\overset{a_2}{\to }}{s}_2\underset{r=0}{\overset{a_3}{\to }}{s}_5\underset{r=0}{\overset{a_3}{\to }}{s}_8\underset{r=1}{\overset{a_2}{\to }}{s}_9$$

Return (回报): 针对一个Trajectory，将所有的reward累和，因此又称为total rewards或cumulative rewards。

1. 可以用来评估一个policy的好坏(和比较两policy)。
2. Return包含immediate reward和future rewards。其中immediate reward是在初始state (initial state)采取action后立即获得的reward，future rewards指离开initial state后获得的rewards总和。
3. 为避免短视(short-sighted)的决定，应该关注return而不是immediate reward。

Discounted return (折扣回报): 一个trajectory有时是无穷的，例如当达到目的地后可能“原地踏步”，如果此时仍然有施加reward就会导致 $return\to \infty$，此时可以给每一步的reward施加一个“折扣”(discount) $\gamma \in [0,1)$，第k个reward $r_k$ 变成 ${\gamma }^k{r}_k$。

1. 由于 $\gamma <1$，所以最后的return不会发散。
2. 通过控制 $\gamma$ 的大小，可以控制模型更关注前面的($\gamma$小，短视) action还是未来的($\gamma$大，远视) action。

Episode/Trial (回合/试验): 通常当一个任务会终止时（存在terminal states），即有限长度的Trajectory被称为Episode/Trial。这样的任务被称为episodic task。当不存在terminal states时，这种任务被称为continuing tasks。一般来说没有绝对的一直持续的任务，但是根据解决问题的时间尺度可以这样设置。事实上有统一的方法描述episodic和continuing task，例如

1. 将terminal states看作特殊的state，到达target state后通过设计action space /设计某条件概率为1强制“原地踏步”，并且同时设置之后的reward=0，这样的state称为absorbing states。
2. 就把terminal state当成一个普通的state，达到terminal state的reward设计为正。这样做更具有一般性，且有可能跳出局部最优解。本课程使用2。

Markov decision process (MDP)

马尔可夫决策过程(Markov decision processes, MDPs)是描述随机动力学系统的通用框架，由于在agent与环境交互过程中具有随机性，因此强化学习事实上也可以形式化入MDP框架，其中关键组成部分如下（同时也作为对前面内容的总结回顾）：

1. 集合 (Sets)

   • State space (状态空间)： state的集合，记为 $S$
   • Action space (动作空间)： action的集合，与state有关，记为 $A(s)$
   • Reward set (奖励集合)： reward的集合，与state和action都有关，记为 $R(s,a)$

2. 模型 (Model)

   • State transition probability (状态转移概率)： 在某state采取某action后，state转变为 $s^{\prime }$ 的概率记为 $p(s^{\prime }|s,a)$，其需要满足 $$\sum _{s^{\prime }\in S}p(s^{\prime }|s,a)=1,\forall (s,a)$$
   • Reward probability (奖励概率)： 在某state采取某action后获得reward $r$ 的概率记为 $p(r|s,a)$，其需要满足 $$\sum _{r\in R(s,a)}p(r|s,a)=1,\forall (s,a)$$

3. 马尔可夫性 (Markov property)： 指随机过程的一种无记忆属性(memoryless property)，这里指下一步的state和reward都与前面的state和action无关

   $$p(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...,s_0,a_0)=p(s_{t+1}|s_t,a_t)(1a)$$ $$p(r_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...,s_0,a_0)=p(r_{t+1}|s_t,a_t)(1b)$$

Note 1. 对于所有的 $(s,a)$，$p(s^{\prime }|s,a)$ 和 $p(r|s,a)$ 被称为model / dynamics，其可以是时变/非稳定的(time-variant / nonstationary)也可以是非时变/稳定的(time-invariant/stationary)。环境可以随时间变化的就是时变的，例如在grid world中某些时候某些区域会变成forbidden area。

Note 2. 当Markov decision process中的decision/policy确定了，那么其就等同马尔可夫过程(Markov process, MP)。因为在MDP中包含了具有概率性的model，但是MP只是一个确定性的过程。

Summary

强化学习是agent与environment不断交互的过程。Agent是一个可以感知当前状态（state）、维护改进策略（policy）和执行动作（action）的决策者（decision-maker）。Agent执行动作会改变其state，同时会获得reward，再执行动作依此循环，形成了强化学习的整个流程。

agent take action → execute → state changed + reward obtained → take action → ···

Q & A

Q1: 可以将所有的reward设置为负吗？ A1: 可以。事实上，对一个action鼓励/不鼓励是由reward的相对值而不是绝对值决定。因此将所有的reward设置为负但不同的action有差别仍会找到最优policy。

Q2: reward是下一state $s^{\prime }$ 的函数吗？ A2: 不是。虽然直觉上来说下一个状态 $s^{\prime }$ 的好坏决定这一reward的相对值，但是实际上reward仅是当前state $s$ 和action $a$ 的函数。原因在于 $s^{\prime }$ 也决定于 $s,a$，并且数学上有

$$p(r|s,a)=\sum _{s^{\prime }}p(r|s,a,s^{\prime })p(s^{\prime }|s,a)(2)$$

因此我们使用 $p(r|s,a)$ 而不是 $p(r|s,a,s^{\prime })$。