机器学习：强化学习的epsilon贪心算法

强化学习（Reinforcement Learning, RL）是一种机器学习方法，旨在通过与环境交互，使智能体（Agent）学习如何采取最优行动，以最大化某种累积奖励。它与监督学习和无监督学习不同，强调试错探索（Exploration-Exploitation）以及基于奖励信号的学习。

强化学习任务通常用马尔可夫决策过程来描述：机器处于环境$E$中，状态空间$X$，其中每个状态$x\in X$是机器感知到的环境的描述，机器能采取的动作构成了动作空间$A$，若某个动作$a\in A$作用在当前状态$x$上，则潜在的转移函数$P$将使得环境从当前状态按照某种概率转移到另一个状态，在转移到另一个状态的同时，环境会根据潜在的“奖赏”函数$R$反馈给机器一个奖赏。

在环境中状态的转移、奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。

机器要做的是通过在环境中不断地尝试而学得一个“策略”，根据这个“策略”在状态$x$下就能知道要执行得动作。

在强化学习任务中，学习的目的就是要找到能使长期累积奖赏最大化的策略。

强化学习与监督学习来说，强化学习是没有人直接告诉机器在什么状态下应该做什么动作，只有等到最终结果揭晓，才能通过“反思”之前的动作是否正确来进行学习，因此，强化学习在某种意义上可看作具有“延迟标记信息”的监督学习问题。

强化学习任务的最终奖赏是在多步动作之后才能观察到，这里考虑简单情形：最大化单步奖赏，即仅考虑一步操作。单步强化学习任务对应了一个理论模型：k-摇臂赌博机。

k- 摇臂赌博机：有k个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

若仅为获知每个摇臂的期望奖赏，则可采用“仅探索”法：将所有的尝试机会平均分配给每个摇臂，最后以每个摇臂各自的平均吐币概率作为其奖赏的近似评估。若仅为执行奖赏最大的动作，则可采用“仅利用”法：按下目前最优的摇臂。“仅探索”法会失去很多选择最优摇臂的机会；“仅利用”法可能经常选不到最优摇臂。

$ϵ$贪心法是基于一个概率来对探索和利用进行折中：每次尝试时，以$ϵ$的概率进行探索，以$1-ϵ$的概率进行利用。

则平均奖赏为：
$$Q(k)=\frac{1}{n}\sum _{i=1}^n{v}_i$$
可以改成增量计算：
$$\begin{gathered} Q_n(k)=\frac{1}{n}((n-1)\times Q_{n-1}(k)+v_n) \\ =Q_{n-1}(k)+\frac{1}{n}(v_n-Q_{n-1}(k)) \end{gathered}$$

代码

k-摇臂赌博机实现：

import numpy as npclass KArmedBandit:def __init__(self, k=10, true_reward_mean=0, true_reward_std=1):"""k: 摇臂数量true_reward_mean: 奖励均值的均值true_reward_std: 奖励均值的标准差"""self.k = kself.q_true = np.random.normal(true_reward_mean, true_reward_std, k)  # 每个摇臂的真实均值def step(self, action):"""执行动作（拉某个摇臂），返回奖励"""reward = np.random.normal(self.q_true[action], 1)  # 以 q*(a) 为均值的正态分布return reward

$ϵ$贪心实现：

from data_processing import KArmedBandit
import numpy as np
import matplotlib.pyplot as pltdef select_action(epsilon:float, q_estimates:np.ndarray):"""根据 epsilon-greedy 策略选择动作"""if np.random.rand() < epsilon: # 随机选择return np.random.choice(len(q_estimates))  # else:return np.argmax(q_estimates)  # 选择估计奖励最高的动作
def update_estimates(q_estimates:np.ndarray, action:int, reward:float, action_counts:np.ndarray):"""更新动作的估计奖励"""action_counts[action] += 1q_estimates[action] += (reward - q_estimates[action]) / action_counts[action]return q_estimates, action_countsdef start(k:int, epsilon:float, epochs:int, stps:int):"""开始运行 epsilon-greedy 算法"""q_estimates = np.zeros(k)  # 每个摇臂的估计奖励action_counts = np.zeros(k)  # 每个摇臂被选择的次数avg_rewards = np.zeros(stps)  # 记录每次拉摇臂的奖励for epoch in range(epochs):bandit = KArmedBandit(k)rewards = []for step in range(stps):action = select_action(epsilon, q_estimates)reward = bandit.step(action)q_estimates, action_counts = update_estimates(q_estimates, action, reward, action_counts)rewards.append(reward) # 记录奖励avg_rewards += np.array(rewards) # 记录每次拉摇臂的奖励avg_rewards /= epochsreturn avg_rewardsif __name__ == '__main__':k = 10epsilon = 0.1epochs = 2000stps = 1000avg_rewards = start(k, epsilon, epochs, stps)plt.plot(avg_rewards)plt.xlabel('Steps')plt.ylabel('Average reward')plt.title('RL: epsilon-greedy Performance')plt.show()

深入理解强化学习（一）- 概念和术语 - 知乎 (zhihu.com)