Python 运筹优化12 eps greedy 解读

说明

Epsilon-Greedy（ε-Greedy）是一种用于解决多臂LH机问题（Multi-Armed Bandit Problem）的策略，通常在强化学习中使用。在多臂LH机问题中，有多个选项（臂），每个选项都有一个不同的奖励概率分布，目标是找到一个最佳的策略来最大化总体奖励。

Epsilon-Greedy 算法基于以下思想：

在每个时刻，以概率 ε（epsilon）选择一个随机的动作，称为“探索”。在以概率 1-ε 选择当前已知的最佳动作，称为“利用”。通过这种方式，ε-Greedy 在探索（尝试新动作）和利用（选择已知最佳动作）之间进行权衡，以便在尽量不错过最佳动作的同时，也能够发现新的潜在最佳动作。

内容

0 基础对象

ad 基础对象，通过display_ad来获得奖励

class BernoulliBandit(object):
    def __init__(self, p):
        self.p = p
    
    def display_ad(self):
        reward = np.random.binomial(n=1, p=self.p)
        return reward

1 参数

在这段代码中，ε 的值被设置为 0.1，表示有 10% 的概率进行随机选择，而有 90% 的概率选择当前已知的最佳动作。

n_prod 表示总的尝试次数，n_ads 是广告的数量（即臂的数量）。Q 是每个臂的估计值，N 是每个臂被选择的次数。total_reward 是累计奖励，avg_rewards 是用于存储每次尝试的平均奖励的列表。

eps = 0.1
n_prod = 100000
n_ads = len(ads)
Q = np.zeros(n_ads)
N = np.zeros(n_ads)
total_reward = 0
avg_rewards = []

下面进行迭代

ad_chosen = np.random.randint(n_ads)
for i in range(n_prod):
    R = ads[ad_chosen].display_ad()
    N[ad_chosen] += 1
    Q[ad_chosen] += (1 / N[ad_chosen]) * (R - Q[ad_chosen])
    total_reward += R
    avg_reward_so_far = total_reward / (i + 1)
    avg_rewards.append(avg_reward_so_far)
    
    # Select the next ad to display
    if np.random.uniform() <= eps:
        ad_chosen = np.random.randint(n_ads)
    else:
        ad_chosen = np.argmax(Q)

df_reward_comparison['e-greedy: {}'.format(eps)] = avg_rewards

这段代码是一个使用 ε-Greedy 算法进行多臂LH机问题求解的示例。在每一次尝试中，根据 ε 的概率选择随机动作或者选择当前已知的最佳动作。

ad_chosen = np.random.randint(n_ads)：在初始时随机选择一个广告作为初始动作。

for i in range(n_prod):：循环 n_prod 次，模拟尝试的次数。

R = ads[ad_chosen].display_ad()：显示选择的广告并获取奖励。

N[ad_chosen] += 1 和 Q[ad_chosen] += (1 / N[ad_chosen]) * (R - Q[ad_chosen])：更新选择的广告的次数和估计值。

total_reward += R：累计奖励。

avg_reward_so_far = total_reward / (i + 1)：计算到目前为止的平均奖励。

avg_rewards.append(avg_reward_so_far)：将平均奖励添加到列表中，以便后续分析。

接下来是选择下一个广告的步骤：

if np.random.uniform() <= eps:：以 ε 的概率进行随机选择。
ad_chosen = np.random.randint(n_ads)：如果随机数小于等于 ε，就随机选择一个广告。
else:：否则，选择当前已知最佳的广告。
ad_chosen = np.argmax(Q)：选择当前估计值最高的广告。
最后，df_reward_comparison['e-greedy: {}'.format(eps)] = avg_rewards 将每次尝试的平均奖励添加到数据帧 df_reward_comparison 中，用于后续比较不同算法的效果。

这段代码是一个完整的基于 ε-Greedy 算法的多臂LH机解决方案，可以用于选择最优的广告展示策略。

2 画图

greedy_list = [ 'e-greedy: 0.1']
df_reward_comparison[greedy_list].iplot(title="ε-Greedy Actions",
                                    dash = ['solid'], #, 'dash', 'dashdot', 'dot'],
                                    xTitle='Impressions', 
                                    yTitle='Avg. Reward')

在这里插入图片描述

3 总结

主要的精华部分在这一段，有点像拒绝采样。eps就是选择的不确定性，通过这个来进行随机游走。

    # Select the next ad to display
    if np.random.uniform() <= eps:
        ad_chosen = np.random.randint(n_ads)
    else:
        ad_chosen = np.argmax(Q)