1．MDPs问题-寻宝
Pacman除了吃豆子之外，有时也去以下的Gridworld岛去寻宝。Pacman有一张地图，上面标有那里是hazards，那里是treasure。在地图中任何空的方块，Pacman可以执行标准的 actions (N, S, E, W)，而且这些actions不受移动噪音的影响。当Pacman落入一个 hazard (H) 方块或一个treasure (T) 方块时，它能做的action只有airlift (X)，即把Pacman带入“Done” 状态；如果它是从H出来，reward是-64，而如果它是从T出来，reward是+128，但没有“living reward”（即没有所谓的“生命”reward）。
a) 如果γ = 0.5，求 grid中每个state的V ∗ 值(Optimal value)
b) optimal policy是什么?
我们上面的policy称为
来探寻这个岛到底是什么样的。因为Pacman认为
基于(b)的
来随机选择不同actions.否则，Pacman根据
这个policy称为
基于
择基于概率的，而不是policy所推荐的那个。随机policy可写为π(s,a)，即
表示当agent在状态s时，选择action a的概率。
c) 如果policy π(s,a) 是随机的，写出修改后的用来计算policy的 Bellman equation：
事实证明，Pacman的地图基本上是正确的，只是有些火坑已经变成空的方块。这样，
Pacman开始做Q-Learning,它观察到以下的episodes:
[ (0, 0), N, 0, (0, 1), N, 0, (0, 2), X, 128, Done ]
[ (0, 0), N, 0, (0, 1), N, 0, (0, 2), X, 128, Done ]
[ (0, 0), N, 0, (0, 1), E, 0, (1, 1), X, -64, Done ]
d) 假设Pacman把Q-value初始化为0而且learning rate是1.0，那么在观察到这些
episodes之后，Pacman的Q-values是什么？
2. Search问题– 昆虫重逢
假设你可以控制M x N维的maze环境里的一个或多个昆虫，如下图所示。昆虫每走一步，将进入旁边的North, East, South或West方块，如果旁边方块是空的话；否则昆虫将停留在当前位置。方块可能有墙挡，但地图是已知的。
在回答以下的问题时，你应该回答问题的泛例，而不是简单描述地图所显示的东西。
现在你来控制两个昆虫。你是知道这个maze的环境的，但没有昆虫从哪个方块开始的信息，怎样来帮助这两个昆虫重逢呢？
你可以把这个问题看成一个search问题，这个问题的答案是一个actions的序列，不管昆虫初始位置在什么地方，当昆虫执行了这个序列的actions之后，两个昆虫将会在一个方块中重逢。任何方块都可以，因为两个昆虫只是想重逢，而不在乎在哪个方块。两个昆虫都盲目地执行这些actions,而不知道它们的移动是否成功。如果它们action的执行把它们带向死胡同，那么它们将停留在哪里。两个昆虫每次都可以走一步，每走一步的成本是1.
问题
(a) 给出这个search问题的minimal state representation.
(b) 给出这个search问题的state space的大小。
全部评论
(1) 回帖