AI模型强化学习

经验的积累与利用-Epsilon贪心

字数统计: 2.2k字   |   阅读时长: 8分
,

摘要: Epsilon贪心

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 强化学习环境框架-从一个迷宫环境看MDP的要点 中，我们总结了强化学习的基本概念，以及作为强化学习机制的 MDP，并且以 grid 为例实现了 MDP 环境的代码框架。

有了 MDP 环境之后，我们就要解决如何在其中选择最优行动的问题，也就是 MDP 环境的代码框架中的 agent.policy 方法的实现，具体来说就是价值的计算方法(价值近似)和基于价值近似的行动选择方法(策略)。

当 MDP 环境的迁移函数 transit_func 和奖励函数 reward_func 已知的时候，就可以使用动态规划法来求解。这种基于迁移函数和奖励函数来学习行动的方法称为基于模型的学习方法。在文章 MDP的动态规划解法-策略迭代和价值迭代 中，我们就是从策略迭代和价值迭代两种思路实践的这种动态规划方法。

当不知道环境信息(迁移函数和奖励函数)的情况下，也可以使用这种基于模型的学习方法对这两种函数进行推算，后面我们有机会再探究这种用法。

此外对于环境信息(迁移函数和奖励函数)未知的情况，还有另一种学习方法：无模型的方法。无模型方法通过自身采取行动来积累经验，并根据经验进行学习的方法。

本文我们首先简要说明下无模型的学习方法中，通过行动积累经验的过程中的 3 个要点

  1. 平衡经验的积累与应用
  2. 根据实际奖励来修正计划，还是根据预测来修正计划
  3. 用经验来更新价值近似还是更新策略

然后针对第 1 个问题，也就是平衡经验的积累与应用，详细展开，主要内容是 Epsilon 贪心算法，并以多臂老虎机为例进行实践。第 2 点和第 3 点以后有时间再展开。

通过行动积累经验的 3 个核心问题

(1) 平衡经验的积累与应用

  • 积累经验: 由于迁移函数未知，所以 Agent 能够以多大的概率进行状态迁移也不知道。这样的话，即使智能体与上一次处于同样的状态，采取同样的行动，也可能得到不同的结果。为了对其进行正确估计，有必要积累大量的经验。

  • 利用经验: 积累了经验之后，还需要行动(利用经验)。因为如果不能利用经验，也就无法获得奖励。

于是积累经验和利用经验需要取得平衡。

(2) 根据实际奖励还是预测来修正计划

实际奖励是指立即奖励的总和。

  • 根据实际奖励: 必须在回合结束时进行修正。

  • 根据预测: 智能体状态迁移的过程中，也可以立即根据预测进行修正。

注意，是根据实际奖励，还是根据预测来修正计划，这个讨论只在回合能够结束的情况下成立，这种情况称为回合制任务。回合不能结束的情况称为连续性任务。

(3) 用经验来更新价值近似还是策略

这是在文章 MDP的动态规划解法-策略迭代和价值迭代 中我们讨论过的基于价值和基于策略的观点。

  • 在基于价值的观点下，经验用于价值的更新。
  • 在基于策略的观点下，经验用于策略的更新。

通过行动积累经验的三组问题对比如下图

平衡经验的积累与应用 — Epsilon 贪心

在环境信息(迁移函数和奖励函数)未知的情况下，可以通过自身行动来调查状态迁移或所得的奖励。

当以调查为目的时，应该尽可能地在各种状态下采取各种行动，但这与原本的”奖励最大化”的目标不一样。类似于在游戏中，构建完整地图和尽快逃离地图的目标不一样。

应该采取多少以调查为目标的行动，多少以奖励最大化为目标的行动。这就是探索与利用的折中。

如果能够采取无穷多的行动，肯定是彻底探索之后再利用更好。但是行动总数一般是有限制的。在多臂老虎机问题中，有几台不同的老虎机，在期望后的最多硬币的情况下，玩家能够玩的回合数由余额决定，因此需要金身决定多少预算用于探索，多少预算用于玩老虎机获得硬币。

Epsilon 贪心是用于平衡折中的算法。它以 Epsilon 为概率采取行动进行探索，此外的行动用于利用。

下面以多臂老虎机问题为例，看看 Epsilon 贪心的实现。

多臂老虎机问题

从一些硬币中选出一枚硬币，然后进行一次抛掷，掷出正面朝上就可以获得奖励。

各枚硬币正面朝上的概率不一样，因此为了奖励最大化，应该尽早通过探索发现正面朝上概率高的硬币。

这个问题称为多臂老虎机问题。

这个问题在推荐系统中是一个很重要的问题。在推荐系统中，有两类问题与多臂老虎机问题有关。

一个是冷启动，也就是面对新用户时的时候的策略，我们需要解决如何能够通过若干次实验，猜出用户的大致兴趣。

另一个是 Exploit-Explore，其中 Exploit 表示迎合用户已经确定的兴趣。Explore 表示探索用户的新兴趣。

为了解决多臂老虎机问题。最好的办法是去试一试，但不是盲目地试，而是有策略地快速试一试，这些策略称为 Bandit算法。

Epsilon 贪心是基本的 Bandit 算法。此外还有一些其它的常见的 Bandit 算法，例如 Thompson 采样，UCB(Upper Confidence Bound, 置信区间上界)。

在多臂老虎机问题上实现 Epsilon 贪心

游戏的代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class CoinToss():
    def __init__(self, head_probs, max_episode_steps=30):
        self.head_probs = head_probs
        self.max_episode_steps = max_episode_steps
        self.toss_count = 0

    def __len__(self):
        return len(self.head_probs)

    def reset(self):
        self.toss_count = 0

    def step(self, action):
        final = self.max_episode_steps - 1
        if self.toss_count > final:
            raise Exception("The step count exceeded maximum. \
                            Please reset env.")
        else:
            done = True if self.toss_count == final else False

        if action >= len(self.head_probs):
            raise Exception("The No.{} coin doesn't exist.".format(action))
        else:
            head_prob = self.head_probs[action]
            if random.random() < head_prob:
                reward = 1.0
            else:
                reward = 0.0
            self.toss_count += 1
            return reward, done

head_probs 指定各枚硬币正面朝上的概率。
max_episode_steps 表示投掷次数。

下面是基于 Epsilon 贪心算法行动的智能体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class EpsilonGreedyAgent():
    def __init__(self, epsilon):
        self.epsilon = epsilon
        self.V = []

    def policy(self):
        coins = range(len(self.V))
        if random.random() < self.epsilon:
            return random.choice(coins)
        else:
            return np.argmax(self.V)

    def play(self, env):
        # 初始化估计值
        N = [0] * len(env)
        self.V = [0] * len(env)

        env.reset()
        done = False
        rewards = []
        while not done:
            selected_coin = self.policy()
            reward, done = env.step(selected_coin)
            rewards.append(reward)

            n = N[selected_coin]
            coin_average = self.V[selected_coin]
            new_average = (coin_average * n + reward) / (n + 1)
            N[selected_coin] += 1
            self.V[selected_coin] = new_average

        return rewards

policy 是 Epsilon 贪心的实现。
V 保存各个硬币的期望值。
play 实际进行游戏。

下面进行实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
    env = CoinToss([0.1, 0.5, 0.1, 0.9, 0.1])
    epsilons = [0.0, 0.1, 0.2, 0.5, 0.8]
    game_steps = list(range(10, 310, 10))
    result = {}
    for e in epsilons:
        agent = EpsilonGreedyAgent(epsilon=e)
        means = []
        for s in game_steps:
            env.max_episode_steps = s
            rewards = agent.play(env)
            means.append(np.mean(rewards))
        result["epsilon={}".format(e)] = means
    result["coin toss count"] = game_steps
    result = pd.DataFrame(result)
    result.set_index("coin toss count", drop=True, inplace=True)
    result.plot.line(figsize=(10, 5))
    plt.show()

if __name__ == "__main__":
    main()

如代码中所示，共 5 枚硬币，正面概率分别为 0.1, 0.5, 0.1, 0.9, 0.1，实验的 epsilon 分别为 0.0, 0.1, 0.2, 0.5, 0.8。

实验结果如下，可以看到，对于 0.0, 0.5, 0.8，增加投掷次数的增加与否对奖励的影响不大。而 0.1, 0.2，增加投掷次数还是能带来奖励的提升的。

epsilon 通常取 0.1。有时也会随着学习将 epsilon 逐步下降。

Share