从K-摇臂*开始(java算法概率分布使奖励最大化)
0 K-摇臂*
如图所示，我们有几个单臂*，组成一起我们就称作多臂*，那么我们需要制定什么样的策略才能最大化得到的奖励。这里假设每个*奖励的随机分布是不一样的。
比如第一个分布，D1这个*的分布大概率落在中间这部分，很小概率在两头的地方。假设用户是知道这些分布的，那么用户应当怎么选择？答案很简单，我们应当选择D5这个*，因为它的平均值最高，而且有很大概率在靠右也就是正数范围内。但现在的问题是，用户实际上是不知道这些*的概率分布的。那么我们需要一次次的尝试，尽可能快速的找到这五个*的分布，并利用最佳的分布最大化收益。
1 几个概念
在k臂*中，k个动作中的每一个在被选择时都有一个期望或者平均收益，我们称这个动作为“价值”
如果你持续对动作的价值进行估计，那么在任意一时刻都至少会有一个动作的估计价值时最高的，我们将这些对应的最高估计称为“贪心”动作
从这些动作中选择时，我们称此为“开发”当前你所知道的关于动作的价值的知识
如果选择的是非贪心的动作时，我们则称此为“试探”
2 E-贪心
贪心动作总是利用当前的知识最大化眼前利益，这种方法根本不花时间去尝试明显的劣质动作，看看他们是否会更好，贪心策略的一个简单的代替策略是大部分时间表现的贪心，但偶尔（比如用一个很小的概率E）以独立于动作-价值的方式从所有动作中等概率的做出选择，我们将此方法就称为E-贪心方法。
# e-greedy import math import numpy as np import matplotlib.pyplot as plt import random from random import gauss class Kbandits(object): ''' k-臂*，初始化： k个*的真实价值 q*(At) 服从是均值是0，方差是1 的正太分布 他们的实际收益 rt 是 q*(At) 为均值，方差为1 的正太分布 ''' def __init__(self, k): mean = 0 variance = 1 self.qat = [gauss(mean, math.sqrt(variance)) for i in range(int(k))] self.eps = 0.01 def gen_rewards(self, k): qat = self.qat[k] # mean variance = 1 # variance reward = gauss(qat, math.sqrt(variance)) return reward T = 1000 # 迭代次数 K = 10 # K - 臂* Kbandits = Kbandits(K) r = 0 r_all = [] Q = list([0]*K) count = list([0]*K) for t in range(T): rande = random.random() if rande < Kbandits.eps: k = list(np.random.randint(K, size=1))[0] else: k = np.argmax(Q) v = Kbandits.gen_rewards(k) r = (r*t + v)/(t+1) r_all.append(r) # 画图 Q[k] = (Q[k]*count[k] + v)/(count[k]+1) count[k] = count[k] + 1 print(r) plt.plot(list(range(T)),r_all,color='r') plt.show() ''' 纯贪心的算法只要删除 eps 的比较即可即在循环中： for t in range(T): k = np.argmax(Q) v = Kbandits.gen_rewards(k) r = (r*t + v)/(t+1) r_all.append(r) # 画图 Q[k] = (Q[k]*count[k] + v)/(count[k]+1) count[k] = count[k] + 1 ''' # 您可以通过以上代码测试，K 臂*，作为 e-greedy 与 greedy方式的优越性3 E-贪心，增量式
迄今为止，我们现在讨论的动作-价值方法都是把动作价值作为观测到的收益的样本均值来看待的，比如：我们在代码中的 v 就是当前动作的价值，我们直接选择了该v作为选择的依据，但是实际上，我们每一次操作是抽样，应该计算每一个*的样本均值作为决策的最终依据。
Q值的跟新公式一般变成： 新估计值 <<< 旧估计值 + 步长 * [目标 - 旧估计值]；表达式[目标 - 估计值]是估计值的无擦汗，误差会随着向目标靠近的每一步而减小
4 跟踪一个非平稳问题
前面讨论的问题是一个不变的问题，即你所玩的游戏所获得的收益每次都变化不大，但是如果赌博机的收益随着时间不断变化，那么我们需要增加当前的收益的权重，以表示我们对当前收益影响的重视。
其中alpha的大小属于(0,1]，且是一个常数
5 基于置信度上界的动作选择（UCB）
因为对动作-价值的估计总会存在不确定性，所以试探是必须的。贪心动作虽然再当前时刻看卡来最好，但是实际上，其他一些动作实际上从长远来看要更好。egreedy的方式会尝试非贪心的动作，但是这是一种盲目的选择，因为他不太会去选择接近贪心或者不确定性特别大的动作。在非贪心的动作中，最好是根据他们的潜力来选择可能事实上最有的动作，这就要考虑他们的估计有多接近最大值，以及这些估计的不确定性。
N_t(a)表示在时刻t之前动作a被选择的次数，如果N_t(a)==0，则a就被认为是满足最大化条件的动作，需要注意的时，到目前为止使用UCB进行复杂问题的求解时，目前还没有已知的方法利用UCB选择的思想，主要问题是处理非平稳问题时。
import math import numpy as np import matplotlib.pyplot as plt import random from random import gauss class Kbandits(object): ''' k-臂*，初始化： k个*的真实价值 q*(At) 服从是均值是0，方差是1 的正太分布 他们的实际收益 rt 是 q*(At) 为均值，方差为1 的正太分布 ''' def __init__(self, k): mean = 0 variance = 1 self.qat = [gauss(mean, math.sqrt(variance)) for i in range(int(k))] self.eps = 0.01 def gen_rewards(self, k): qat = self.qat[k] # mean variance = 1 # variance reward = gauss(qat, math.sqrt(variance)) return reward def egreedy(self, rande, Q): if rande < Kbandits.eps: k = list(np.random.randint(K, size=1))[0] else: k = np.argmax(Q) return k def greedy(self, Q): k = np.argmax(Q) return k def UCB(self, Q, count, t): R = [] c = 2 for q in range(len(Q)): if count[q] == 0: count[q] = count[q] + 1 return q else: r = Q[q]+c*(math.sqrt(math.log(t, 2.71828)/count[q])) R.append(r) print(t, r) return np.argmax(R) T = 1000 # 迭代次数 K = 10 # K - 臂* Kbandits = Kbandits(K) r = 0 r_all = [] Q = list([0]*K) count = list([0]*K) for t in range(1,T+1): rande = random.random() # algorithm # k = Kbandits.egreedy(rande, Q) # K: egreedy # k = Kbandits.egreedy(Q) # K: greedy k = Kbandits.UCB(Q, count, t) v = Kbandits.gen_rewards(k) r = (r*t + v)/(t+1) r_all.append(r) # 画图 Q[k] = (Q[k]*count[k] + v)/(count[k]+1) count[k] = count[k] + 1 plt.plot(list(range(T)),r_all,color='r') plt.show()
本文地址：https://blog.csdn.net/qq_36336522/article/details/107037337