[PYTHON] [Lernen stärken] Banditenaufgabe

Einführung

$ N $ Skill Bandit Task in Python implementiert. Als Lehrbuch ["Stärkung des Lernens"](http://www.amazon.co.jp/ Stärkung des Lernens - Richard-S-Sutton / dp / 4627826613 / ref = sr_1_1? Dh = UTF8 & qid = 1463965873 & sr = 8-1 & keywords = Stärkung des Lernens % E3% 80% 80 Mikami) wurde verwendet.

Struktur dieses Artikels

• Einführung
• Verbessertes Lernen
• Überblick
• Komponente
• Banditenaufgabe
• Regeln
• Beispielmittelungsmethode
• Aktionsauswahlregeln
• Implementierung
• Ergebnis
• abschließend

Lernen stärken

Überblick

Das Intensivierungslernen lernt, welche Aktionen ausgewählt werden müssen, um die Belohnungen zu maximieren. Beim überwachten Lernen erhalten Sie die richtige Aktion zur Auswahl, beim erweiterten Lernen wählen Sie eine Aktion basierend auf einer "bestimmten Richtlinie" aus und bewerten und aktualisieren die Aktion anhand der daraus erhaltenen Belohnungen. Sie können Ihre Belohnung maximieren, indem Sie gemäß den erlernten "bestimmten Richtlinien" handeln.

Komponente

Ich werde die Komponenten des verstärkenden Lernens und ihre kurzen Erklärungen erläutern.

• Agent: Eine Person, die die Umgebung wahrnimmt und direkt mit der Umgebung interagiert
• Umgebung: Umgebung unabhängig vom Agenten
• Belohnung: Wert, der durch die Aktion des Agenten aus der Umgebung erhalten wird
• Wertfunktion: Die Gesamtmenge an Belohnungen, die in Zukunft basierend auf der aktuellen Situation des Agenten angesammelt werden können

Der Agent erkennt die Umgebung und wählt Aktionen basierend auf dem erfassten Status und der Wertfunktion aus. Die Umgebung gibt die Belohnung für die Aktion zurück und diese Belohnung wird verwendet, um den Wert der Aktion zu aktualisieren.

Banditenaufgabe

Regel

Ein Spielautomat mit $ n $ Hebeln wird als $ n $ Armbandit bezeichnet. Wählen Sie ein $ 1 $ Buch aus den $ n $ Buchhebeln und ziehen Sie den Hebel, um einen Preis zu gewinnen. Zuerst generieren wir eine Belohnung $ Q ^ {\ ast} (a) $ für eine Aktion $ a $ aus einer Gaußschen Verteilung mit einem Durchschnitt von $ 0 $ und einer Varianz von $ 1 $. Als nächstes generieren wir aus der Gaußschen Verteilung mit dem Mittelwert $ Q ^ {\ ast} (a) $ Varianz $ 1 $ die Belohnungen aus der Banditenmaschine. Das Erstellen mehrerer Banditenmaschinen und das Ziehen aller Banditenmaschinen $ 1 $ wird als $ 1 $ Spiel bezeichnet. Maximieren Sie die Belohnungen, indem Sie durch mehrere Spiele lernen.

Beispielmittelungsmethode

Durch Mitteln der Belohnungen, die bei Auswahl einer Aktion erzielt werden, kann der Wert dieser Aktion geschätzt werden. Dies wird als Stichprobenmittelungsmethode bezeichnet. Der wahre Wert der Aktion $ a $ sei $ Q ^ {\ ast} (a) $ und der geschätzte Betrag im $ t $ -ten Spiel sei $ Q_t (a) $. Wenn die Aktion $ a $ im $ t $ -ten Spiel $ k_a $ mal ausgewählt wird und die Belohnungen für jede Auswahl $ r_ {1}, r_ {2}, ..., r_ {k_a} $ sind Der Wert der Aktion $ a $ bis zur Zeit $ t $ ist wie folgt definiert.

Q_{t}(a) = \frac{r_{1} + r_{2} + \cdots + r_{k_a}}{k_a}

In $ k_a \ rightarrow \ infty $ konvergiert es nach dem Gesetz der Mehrheit zu $ Q_t (a) \ rightarrow Q ^ {\ ast} (a) $.

Aktionsauswahlregeln

Die Greedy-Methode und die $ \ varepsilon $ Greedy-Methode werden als Aktionsauswahlregeln erläutert. Die Greedy-Methode wählt die Aktion mit dem höchsten geschätzten Aktionswert aus. Mit anderen Worten, im $ t $ -ten Spiel $ 1 $ gierigen Verhaltens, so dass $ Q_t (a ^ {\ ast}) = \ max_ {a} Q_t (a) $ $ a ^ {\ ast} $ Wählen. Bei der Methode $ \ varepsilon $ Greedy wird eine zufällige Aktion mit einer Wahrscheinlichkeit von $ \ varepsilon $ und eine gierige Aktion mit einer Wahrscheinlichkeit von $ 1- \ varepsilon $ ausgewählt. Die Greedy-Methode wählt immer die Aktion mit dem besten Wert aus und versucht niemals eine andere Aktion. Dies bedeutet, dass Sie keine der Aktionen finden können, die Sie nicht ausprobiert haben und die noch besser sind als das, was Sie derzeit am besten können. Andererseits wird bei der $ \ varepsilon $ Greedy-Methode die Aktion grundsätzlich gierig ausgewählt, aber manchmal wird die Aktion zufällig mit einer Wahrscheinlichkeit von $ \ varepsilon $ ausgeführt. Auf diese Weise können Sie möglicherweise ein noch besseres Verhalten finden als das, was Sie derzeit am besten können.

Implementierung

Ich habe es wie folgt implementiert. Ich habe eine $ 10 $ Banditenmaschine mit $ 2000 $ vorbereitet und durch $ 2000 $ Spiel gelernt. Hier besteht das $ 1 $ -Spiel darin, $ 1 $ für alle Maschinen im $ 2000 $ -Bereich zu ziehen. (Die Ergebnisse unterscheiden sich geringfügig, da einige der Regeln im Lehrbuch geändert wurden.)

bandit.py

import numpy
from matplotlib import pyplot
import random
import sys

class Bandit:

	# constuctor
	def __init__(self, n_machine, n_action):
		for i in range(n_action):
			_qstar = numpy.random.normal(0.0, 1.0)
			_machine = numpy.random.normal(_qstar, 1.0, n_machine).reshape((-1, 1))
			if i == 0:
				self.machine = _machine
			else:
				self.machine = numpy.hstack((self.machine, _machine))


# public method
	def play(self, n_play, epsilon):
		
		self.q = numpy.zeros(self.machine.shape)
		self.q_count = numpy.zeros(self.machine.shape)
		average_reward = numpy.zeros(n_play)
		n_machine = self.machine.shape[0]

		for _p in range(n_play):
			total = 0.0
			for mac_index in range(n_machine):
				act_index = self.__select_action(mac_index, epsilon)
				reward = self.machine[mac_index, act_index]
				total += reward
				self.__update_qtable(reward, mac_index, act_index)

			average_reward[_p] = total / n_machine
			self.__display(_p, average_reward[_p])

		return average_reward


# private method
	def __select_action(self, mac_index, epsilon):
		if numpy.random.rand() > epsilon:
			act_index = self.__select_greedy_action(mac_index)
		else:
			act_index = self.__select_random_action()

		return act_index


	def __select_greedy_action(self, mac_index):
		_max = self.q[mac_index, :].max()
		indexes = numpy.argwhere(self.q[mac_index, :] == _max)
		random.shuffle(indexes)
		return indexes[0]


	def __select_random_action(self):
		return numpy.random.randint(10)


	def __update_qtable(self, reward, mac_index, act_index):
		_q = self.q[mac_index, act_index]
		self.q_count[mac_index, act_index] += 1
		self.q[mac_index, act_index] = _q + (reward - _q) / self.q_count[mac_index, act_index]


	def __display(self, play, average_reward):
		if (play + 1) % 100 == 0:
			print u'play: %d, average reward: %f' % (play + 1, average_reward)

main.py

from bandit import *

if __name__ == '__main__':

	# param
	param = sys.argv

	# init
	n_machine = 2000
	n_action = 10
	n_play = 2000
	epsilon = [0.0, 0.01, 0.1, 1.0]

	# draw init
	mergin = 5
	color = ['b', 'g', 'r', 'k']
	pyplot.figure(figsize = (8, 6))
	pyplot.xlim(-mergin, n_play + mergin)

	# bandit machine
	bandit = Bandit(n_machine, n_action)

	# play
	for i in range(len(epsilon)):
		print u'play count: %d, epsilon: %.2f' % (n_play, epsilon[i])
		average_reward = bandit.play(n_play, epsilon[i])
		_label = 'e = %.2f' % epsilon[i]
		pyplot.plot(numpy.arange(n_play), average_reward, color = color[i], label = _label)
		print '!!!finish!!!\n'

	# save and show
	if '-d' in param or '-s' in param:
		pyplot.legend(loc = 'center right')
		if '-s' in param:
			pyplot.savefig('bandit2.png')
		if '-d' in param:
			pyplot.show()

Ergebnis

Die folgenden Ergebnisse wurden erhalten. Bei $ \ varepsilon = 0.0 $ wählen Sie immer eine gierige Aktion aus. Wenn Sie also eine Aktion im Wert von $ 0 $ oder mehr finden, wählen Sie diese Aktion immer weiter aus. Daher ist der Durchschnittswert der erhaltenen Belohnungen immer konstant. Bei $ \ varepsilon = 1.0 $ wirkt es immer zufällig. Selbst wenn die Anzahl der Spiele zunimmt, überschreitet der Durchschnittswert der Belohnungen, die erhalten werden können, einen bestimmten Bereich nicht. Mit $ \ varepsilon = 0.1 $ gibt es eine $ 10 % $ Chance, zufällig zu handeln, und eine $ 90 % $ Chance, eine gierige Aktion zu wählen. Wir finden das beste Verhalten am schnellsten, aber selbst nach dem Lernen haben wir eine Chance von 10 $%, zufällig zu handeln, sodass die durchschnittliche Belohnung nur bei 1,8 $ liegt. Mit $ \ varepsilon = 0.01 $ gibt es eine $ 1 % $ Chance, zufällig zu handeln, und eine $ 99 % $ Chance, eine gierige Aktion zu wählen. Die Konvergenzgeschwindigkeit ist langsamer als $ \ varepsilon = 0.1 $, aber die Leistung ist die beste aus einem Spiel von ungefähr $ 1000 $.

abschließend

Wir haben die $ n $ Skill Bandit-Aufgabe in Python implementiert und den Unterschied im Lernprozess aufgrund der Änderung in $ \ varepsilon $ bestätigt.