Mehrarmiger Bandit zur allgemeinen Belohnungsverteilung

11

Ich arbeite an einem mehrarmigen Banditenproblem, bei dem wir keine Informationen über die Belohnungsverteilung haben.

Ich habe viele Artikel gefunden, die bedauernde Grenzen für eine Verteilung mit bekannter Bindung und für allgemeine Verteilungen mit Unterstützung in [0,1] garantieren.

Ich möchte herausfinden, ob es eine Möglichkeit gibt, in einer Umgebung, in der die Belohnungsverteilung keine Garantie für ihre Unterstützung bietet, gute Leistungen zu erbringen. Ich versuche, eine nichtparametrische Toleranzgrenze zu berechnen und diese Zahl zum Skalieren der Belohnungsverteilung zu verwenden, damit ich den in diesem Dokument angegebenen Algorithmus 2 verwenden kann ( http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf) ). Glaubt jemand, dass dieser Ansatz funktionieren wird?

Wenn nicht, kann mich jemand auf die richtige Stelle hinweisen?

Vielen Dank!

references multiarmed-bandit Gast
quelle

Antworten:

6

O(log⁡(T))ϵ

Selbst der von Ihnen erwähnte einfache Thompson-Stichprobenalgorithmus erfordert von Bernoulli verteilte Belohnungen, und selbst das hat 80 Jahre gedauert, um eine logarithmische Bedauernsgrenze zu beweisen!

In der Praxis können Sie die Belohnungsverteilung jedoch in Fällen, in denen Sie die Belohnungsverteilung nicht genau kennen, einfach auf skalieren [0,1]SSS:=2S

Außerdem benötigt der von Ihnen erwähnte Thompson-Stichprobenalgorithmus Bernoulli-Versuche, sodass Sie keine willkürlichen kontinuierlichen Belohnungen verwenden können. Sie könnten eine Gaußsche posteriore Verteilung anstelle einer Beta anpassen, dies ist jedoch etwas empfindlich gegenüber Ihrer Wahl des Prior, sodass Sie sie möglicherweise sehr flach einstellen möchten. Wenn Sie nichts über Ihre Implementierung beweisen möchten, funktioniert dies wahrscheinlich recht gut.

Fairidox
quelle
1
Vielen Dank für die Antwort! Ich weiß das wirklich zu schätzen! Ich hatte allerdings eine Frage. Ich denke, Algorithmus 2 auf dem Papier (oben auf Seite 39.4), den ich erwähnt habe, erfordert nichts über die Belohnungsverteilung, ABER die Tatsache, dass seine Unterstützung in [0,1] enthalten ist. Vielleicht haben Sie sich Algorithmus 1 angesehen?
Gast
Ja, cool, ein ziemlich interessanter Trick, um echte Werte in Bernoulli-Samples umzuwandeln, danke, dass Sie darauf hingewiesen haben, dass mir das Detail entgangen ist. In jedem Fall, wie Sie sagen, benötigen Sie immer noch begrenzte Variablen. Sie können dies mit dem von mir erwähnten billigen Doppeltrick tun und diese Version der Thompson-Stichprobe verwenden. Es ist jedoch möglicherweise besser, eine Methode zu formulieren, die einen Gaußschen Posterior verwendet.
Fairidox
Ich werde mich mehr mit der Gaußschen posterioren Methode befassen, aber was meinst du mit "flach" in Bezug auf Gaußsche? Ich würde annehmen, dass das so etwas wie eine Beta (1,1) (Uniform) vorher entspricht, richtig?
Gast
Richtig, aber Sie können offensichtlich keine Uniform vor einer unbegrenzten Domain haben. Wenn Sie also ein Gaußsches posteriores Modell haben, haben Sie wahrscheinlich einen Gaußschen Prior, also möchten Sie es im Allgemeinen so "flach" oder nicht informativ wie möglich haben. Dies bedeutet im Allgemeinen, die Varianz so groß wie möglich zu machen. Ich bin kein Experte, aber es gibt eine ganze Reihe von Studien darüber, wie man uninformative und möglicherweise unangemessene Prioritäten konstruiert, die Sie vielleicht untersuchen möchten. Wenn Sie streng positive Belohnungen haben, sollten Sie auch ein anderes Modell in Betracht ziehen.
Fairidox