策略迭代 (Policy Iteration)

转载自知乎

https://zhuanlan.zhihu.com/p/34006925

 

假设我们有一个3 x 3的棋盘:

  • 有一个单元格是超级玛丽,每回合可以往上、下、左、右四个方向移动
  • 有一个单元格是宝藏,超级玛丽找到宝藏则游戏结束,目标是让超级玛丽以最快的速度找到宝藏
  • 假设游戏开始时,宝藏的位置一定是(1, 2)

策略迭代 (Policy Iteration)

 

这个一个标准的马尔科夫决策过程(MDP):

  • 状态空间State:超级玛丽当前的坐标
  • 决策空间Action: 上、下、左、右四个动作
  • Action对State的影响和回报 P(State', Reward | State, Action):本文认为该关系是已知的
    • 超级玛丽每移动一步,reward = -1
    • 超级玛丽得到宝箱,reward = 0并且游戏结束

利用策略迭代 (Policy Iteration) 求解马尔科夫决策过程

上一篇我们介绍了如何使用价值迭代 (Value Iteration) 来求解MDP,这篇介绍另外一种方法:策略迭代 (Policy Iteration)。

关于策略迭代,需要知道下面几点:

  • 什么叫策略?策略就是根据当前状态决定该采取什么Action, 策略迭代 (Policy Iteration) P(Action | State)
    • 以本文超级玛丽寻找宝箱为例,超级玛丽需要不断朝着宝箱的方向前进
      • 当前状态在宝箱左侧,策略应该是朝右走
      • 当前状态在宝箱上方,策略应该是超下走
  • 如何衡量策略的好坏 —— 策略评估 (Policy Evaluation)
    • 还记得上一节定义的价值函数 (Value Function) 吗?给定一个策略,我们可以计算出每个状态的期望价值 V(s)
  • 如何找到更好的策略 —— 策略迭代 (Policy Iteration)
    • 初始化:随机选择一个策略作为初始值,比如说不管什么状态,一律朝下走,即P(Action = 朝下走 | State) = 1,P(Action = 其他Action | State) = 0
    • 第一步 策略评估 (Policy Evaluation):根据当前的策略计算V(s)
    • 第二步 策略提升 (Policy Improvement):计算当前状态的最好Action,更新策略, 策略迭代 (Policy Iteration)策略迭代 (Policy Iteration)
    • 不停的重复策略评估和策略提升,直到策略不再变化为止

策略迭代 (Policy Iteration)

下面以寻找宝藏为例,说明策略迭代过程:

  • 初始化:无论超级玛丽在哪个位置,策略默认为向下走
    • 策略评估:计算V(s)
      • 如果宝藏恰好在正下方,则期望价值等于到达宝藏的距离(-2或者-1)
      • 如果宝藏不在正下方,则永远也不可能找到宝藏,期望价值为负无穷
    • 策略提升:根据V(s)找到更好的策略
      • 如果宝藏恰好在正下方,则策略已经最优,保持不变
      • 如果宝藏不在正下方,根据 策略迭代 (Policy Iteration) 可以得出最优策略为横向移动一步
  • 第一轮迭代:通过上一轮的策略提升,这一轮的策略变成了横向移动或者向下移动(如图所示)
    • 策略评估:计算V(s)
      • 如果宝藏恰好在正下方,则期望价值等于到达宝藏的距离(-2或者-1)
      • 如果宝藏不在正下方,当前策略会选择横向移动,期望价值为-3, -2, -1
    • 策略提升:根据V(s)找到更好的策略
      • 如果宝藏恰好在正下方,则策略已经最优,保持不变
      • 如果宝藏不在正下方,根据 策略迭代 (Policy Iteration) 可以得出当前策略已经最优,保持不变

源码实现

下面的代码实现了一个Agent,价值迭代在optimize函数中实现,完整可运行jupyter notebook欢迎访问我的Github: whitepaper/RL-Zoo

class Agent:
    def __init__(self, env):
        self.env = env

    def policy_evaluation(self, policy):
        V = np.zeros(self.env.nS)
        THETA = 0.0001
        delta = float("inf")
        
        while delta > THETA:
            delta = 0
            for s in range(self.env.nS):
                expected_value = 0
                for action, action_prob in enumerate(policy[s]):
                    for prob, next_state, reward, done in self.env.P[s][action]:
                        expected_value += action_prob * prob * (reward + DISCOUNT_FACTOR * V[next_state])
                delta = max(delta, np.abs(V[s] - expected_value))
                V[s] = expected_value
        
        return V
    
    def next_best_action(self, s, V):
        action_values = np.zeros(env.nA)
        for a in range(env.nA):
            for prob, next_state, reward, done in self.env.P[s][a]:
                action_values[a] += prob * (reward + DISCOUNT_FACTOR * V[next_state])
        return np.argmax(action_values), np.max(action_values)
    
    def optimize(self):
        policy = np.tile(np.eye(self.env.nA)[1], (self.env.nS, 1))
        
        is_stable = False
        
        round_num = 0
        
        while not is_stable:
            is_stable = True
            
            print("\nRound Number:" + str(round_num))
            round_num += 1
            
            print("Current Policy")
            print(np.reshape([env.get_action_name(entry) for entry in [np.argmax(policy[s]) for s in range(self.env.nS)]], self.env.shape))
            
            V = self.policy_evaluation(policy)
            print("Expected Value accoridng to Policy Evaluation")
            print(np.reshape(V, self.env.shape))
            
            for s in range(self.env.nS):
                action_by_policy = np.argmax(policy[s])
                best_action, best_action_value = self.next_best_action(s, V)
                # print("\nstate=" + str(s) + " action=" + str(best_action))
                policy[s] = np.eye(self.env.nA)[best_action]
                if action_by_policy != best_action:
                    is_stable = False
            
        policy = [np.argmax(policy[s]) for s in range(self.env.nS)]
        return policy

策略迭代的适用场景

使用策略迭代求解MDP问题时,需要满足一下条件(跟价值迭代的应用条件非常类似):

  • Action对State的影响和回报 P(State', Reward | State, Action)是已知的,然而绝大多数实际问题中P(State', Reward | State, Action)是未知的
  • State和Action都是离散取值,无法应对Action或者State是连续取值的
  • State和Action都是低维度离散取值,因为计算复杂度是随着维度的升高而迅速变大的—— O(|State| x |Action| x |State|)

价值迭代 v.s. 策略迭代

借用*的一张图,我们把价值迭代和策略迭代放在一起看:

策略迭代 (Policy Iteration)

把策略迭代和价值迭代放在一起,可以把Value Iteration看成是简化的Policy Iteration:

  • 在Policy Iteration中
    • 第一步 Policy Eval:一直迭代至收敛,获得准确的V(s)
    • 第二步 Policy Improvement:根据准确的V(s),求解最好的Action
  • 对比之下,在Value Iteration中
    • 第一步 "Policy Eval":迭代只做一步,获得不太准确的V(s)
    • 第二步 "Policy Improvement":根据不太准确的V(s),求解最好的Action

本质上,Policy Iteration和Value Iteration都属于Model-based方法,这种方法假设我们知道Action带来的Reward和新状态,即P(s', reward | s, a)。最明显的特点是,不用玩迷宫游戏,便能根据转移矩阵计算出最优策略。

上一篇:强化学习PARL——4. 基于策略梯度方法求解RL


下一篇:强化学习(Reinforcement learning)综述