当前位置： 移动技术网 > IT编程>脚本编程>Python > 强化学习从K-摇臂老虎机开始

强化学习从K-摇臂老虎机开始

2020年07月03日  | 移动技术网IT编程  | 我要评论

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网