欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

强化学习(8)-Planning and Learning with Tabular Methods

这一章貌似比较难啃...并且很重要

Models and Planning

这里model指的是环境的模型,环境模型有两大类:

  1. 输入当前状态和行为,输出下一个所有可能状态和奖励的分布
  2. 输入当前状态和行为,输出下一个状态和奖励

Planning可以看做是通过对模型的合理使用,制定"策略",用最低的成本得到收敛的价值函数

Dyna: Integrating Planning, Acting, and Learning

如果我们有了完美的环境模型,就可以使用类似动态规划(Planning)的方法得到收敛的Q,但是我们没有完美的模型.

那么我们是否可以用已知的样本, 学出来一个差不多的环境模型, 然后用这个环境模型学出来一个Q?这当然是可以的, 我们甚至可以学出来这个Q之后, 用这个Q优化策略从而生成更好的样本, 然后更新环境模型和Q;这样,就可以持续的迭代下去.所以更新Q有两个路径,1)环境模型生成的家样本更新; 2)真实的样本更新.

下面两个图更好的理解这个过程:

8.2.1

Dyna-Q算法

上面描述的过程对应的算法:

8.2.2

算法的一张图:

8.2.3

对这个算法,一个直观的理解,通过direct RL学习比较新的知识, 通过 undirect RL巩固已经学到的知识使其处于收敛状态(Planning次数足够多).

Prioritized sweeping

前面Planning搜索是随机的,这里加入了一个优先队列,每次还把变化最大的周围四个(可以直接到达)的加进去, 有点还有点广搜的意思,和最短路算法有相似.

8.2.4

Trajectory Sampling

就是动态规划过程中不计算所有节点,而是选择重要的进行更新.

Heuristic Search

在action选择的时候,通过一定深度的搜索得到最好的路径,在model准确Q不准确的时候可用.

8.2.5

Rollout Algorithms

和上面的树搜索类似,只是搜索的时候随机选择.并且不去更新Q,只是找到比随机更好的action而已

Rollout algorithms are decision-time planning algorithms based on Monte Carlo control applied to
simulated trajectories that all begin at the current environment state. They estimate action values for
a given policy by averaging the returns of many simulated trajectories that start with each possible
action and then follow the given policy. When the action-value estimates are considered to be accurate
enough, the action (or one of the actions) having the highest estimated value is executed, after which
the process is carried out anew from the resulting next state. As explained by Tesauro and Galperin
(1997), who experimented with rollout algorithms for playing backgammon, the term \rollout" comes
from estimating the value of a backgammon position by playing out, i.e., \rolling out," the position
many times to the game's end with randomly generated sequences of dice rolls, where the moves of both
players are made by some xed policy.

Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a recent and strikingly successful example of decision-time planning.

蒙特卡罗搜索树和rollout算法类似,但是他的搜索不是随机选择的,而是有"指导"的搜索, 目的当然是为了更大概率的获得更好的路径.

MCTS也是AlphaGo核心技术之一,同时并不局限于棋类搜索, 所有的可以进行多步高效模拟的问题都可以用这个方法.

MCTS并不是每次都从当前状态开始搜索, 而是会利用以前搜索到的以当前状态为开始状态的高分路径作为候选.

MCTS有四个步骤组成,如下图:

8.2.6

  • backup的之后,rollout的路径不更新价值函数, 只对selection和expansion的路径更新.
  • 上面四个步骤循环执行,直到计算资源/时间耗尽或者没有新的状态
  • 并不是每次都从当前节点开始,而是会复用出现过当前节点树结构

未经允许不得转载:大数据算法 » 强化学习(8)-Planning and Learning with Tabular Methods

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站