欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

从K-摇臂*开始(java算法概率分布使奖励最大化)

程序员文章站 2023-11-27 13:16:16
0 K-摇臂*如图所示,我们有几个单臂*,组成一起我们就称作多臂*,那么我们需要制定什么样的策略才能最大化得到的奖励。这里假设每个*奖励的随机分布是不一样的。比如第一个分布,D1这个*的分布大概率落在中间这部分,很小概率在两头的地方。假设用户是知道这些分布的,那么用户应当怎么选择?答案很简单,我们应当选择D5这个*,因为它的平均值最高,而且有很大概率在靠右也就是正数范围内。但现在的问题是,用户实际上是不知道这些*的概率分布的。那么我们需要一次次的尝试,尽可能快速....

0 K-摇臂*

从K-摇臂*开始(java算法概率分布使奖励最大化)

如图所示,我们有几个单臂*,组成一起我们就称作多臂*,那么我们需要制定什么样的策略才能最大化得到的奖励。这里假设每个*奖励的随机分布是不一样的。

从K-摇臂*开始(java算法概率分布使奖励最大化)

比如第一个分布,D1这个*的分布大概率落在中间这部分,很小概率在两头的地方。假设用户是知道这些分布的,那么用户应当怎么选择?答案很简单,我们应当选择D5这个*,因为它的平均值最高,而且有很大概率在靠右也就是正数范围内。但现在的问题是,用户实际上是不知道这些*的概率分布的。那么我们需要一次次的尝试,尽可能快速的找到这五个*的分布,并利用最佳的分布最大化收益。

1 几个概念

在k臂*中,k个动作中的每一个在被选择时都有一个期望或者平均收益,我们称这个动作为“价值”

如果你持续对动作的价值进行估计,那么在任意一时刻都至少会有一个动作的估计价值时最高的,我们将这些对应的最高估计称为“贪心”动作

从这些动作中选择时,我们称此为“开发”当前你所知道的关于动作的价值的知识

如果选择的是非贪心的动作时,我们则称此为“试探”

2 E-贪心

贪心动作总是利用当前的知识最大化眼前利益,这种方法根本不花时间去尝试明显的劣质动作,看看他们是否会更好,贪心策略的一个简单的代替策略是大部分时间表现的贪心,但偶尔(比如用一个很小的概率E)以独立于动作-价值的方式从所有动作中等概率的做出选择,我们将此方法就称为E-贪心方法。

从K-摇臂*开始(java算法概率分布使奖励最大化)

# 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作为选择的依据,但是实际上,我们每一次操作是抽样,应该计算每一个*的样本均值作为决策的最终依据。

从K-摇臂*开始(java算法概率分布使奖励最大化)

从K-摇臂*开始(java算法概率分布使奖励最大化)

Q值的跟新公式一般变成: 新估计值 <<< 旧估计值 + 步长 * [目标 - 旧估计值];表达式[目标 - 估计值]是估计值的无擦汗,误差会随着向目标靠近的每一步而减小

4 跟踪一个非平稳问题

前面讨论的问题是一个不变的问题,即你所玩的游戏所获得的收益每次都变化不大,但是如果赌博机的收益随着时间不断变化,那么我们需要增加当前的收益的权重,以表示我们对当前收益影响的重视。

从K-摇臂*开始(java算法概率分布使奖励最大化)

其中alpha的大小属于(0,1],且是一个常数

5 基于置信度上界的动作选择(UCB)

因为对动作-价值的估计总会存在不确定性,所以试探是必须的。贪心动作虽然再当前时刻看卡来最好,但是实际上,其他一些动作实际上从长远来看要更好。egreedy的方式会尝试非贪心的动作,但是这是一种盲目的选择,因为他不太会去选择接近贪心或者不确定性特别大的动作。在非贪心的动作中,最好是根据他们的潜力来选择可能事实上最有的动作,这就要考虑他们的估计有多接近最大值,以及这些估计的不确定性。

从K-摇臂*开始(java算法概率分布使奖励最大化)

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

相关标签: java算法