Problème de bandit multi-armé

emballer

J'ai essayé de résoudre le problème des bandits à plusieurs bras avec Thompson Sampling.

Quel est le problème du bandit multi-armé?

(Dans le cas de Bernoulli Bandit) Il existe plusieurs machines à sous, et lorsque vous y jouez, vous obtenez des succès et des ratés. La probabilité de gagner est différente pour chaque créneau, mais la valeur est inconnue. En ce moment, je veux gagner beaucoup avec le nombre fixe de gameplays.

Cela s'appelle Bernoulli Bandit La distribution discrète avec une probabilité p de 1 et p-1 de 0 est [distribution de Bernouy](https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%8C % E3% 83% BC% E3% 82% A4% E5% 88% 86% E5% B8% 83) C'est pourquoi.

Comme image à résoudre,

Qu'est-ce que l'échantillonnage Thompson?

Un des algorithmes pour résoudre le problème du bandit multi-armé.

La distribution bêta ici est que lorsque la distribution de probabilité est la distribution de Bernoulli comme celle-ci, Si la distribution a priori est une distribution bêta, la probabilité postérieure est également une distribution bêta, Il semble que ce soit une distribution a priori conjuguée [2]

Je l'ai implémenté comme ça.

self.results n'a besoin que de Sat et Fat, mais je le garde car je pourrais l'utiliser plus tard.

import scipy
import scipy.stats
import numpy.random
import collections
import pprint


# Banding machine simulator.
def getResult(prob):
    return scipy.stats.bernoulli.rvs(prob, size=1)[0]

# Multiarm Bandit Problem solver using Thompson Sampling.
class BernoulliBandit:
    def __init__ (self, numBandits):
        self.numBandits = numBandits
        self.results = dict([(i, []) for i in range(self.numBandits)])
        
    def getBandit(self):
        posteriors = []
        for b in range(self.numBandits):
            Sat = len([r for r in self.results[b] if r == 1])
            Fat = len([r for r in self.results[b] if r == 0])    
            posteriors.append(numpy.random.beta(Sat+1, Fat+1))
        return numpy.array(posteriors).argmax()
    
    def feed(self, selectedBandit, result):
        self.results[selectedBandit].append(result)
        
    def __str__(self):
        out = ""
        for b in range(self.numBandits):
            Sat = len([r for r in self.results[b] if r == 1])
            Fat = len([r for r in self.results[b] if r == 0])    
            out += "Bandit[%d]   Fails: %4d\t  Successes: %6d\n" % (b, Sat, Fat)
        return out

if __name__ == "__main__":
    # set parameters
    numBandits = 3
    numTrials = 5000
    rewards = [0.9, 0.9, 0.4]   # expected rewards (hidden)

    bandit = BernoulliBandit(numBandits)
    for t in range(numTrials):
        if t % 100 == 0:
            print t,
        b = bandit.getBandit()
        r = getResult(rewards[b])
        bandit.feed(b, r)
    print
    print bandit
    print "Rewards", rewards

Le résultat de l'exécution est le suivant. Je n'ai pas répondu aux vraies attentes de récompense, Qu'est-ce qu'une implémentation naïve comme celle-ci? Ou est-ce une erreur de mise en œuvre?

0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900
Bandit[0]   Fails:  250	  Successes:     40
Bandit[1]   Fails: 4261	  Successes:    446
Bandit[2]   Fails:    0	  Successes:      3

Rewards [0.9, 0.9, 0.4]

jupyter gist

Les références

  1. http://ibisml.org/archive/ibis2014/ibis2014_bandit.pdf
  2. http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf

Recommended Posts

Problème de bandit multi-armé
Problème de probabilité