Markov-Entscheidungsprozess: gleiche Aktion führt zu verschiedenen Zuständen

Question

Letzte Woche habe ich eine Arbeit gelesen, die MDP als eine alternative Lösung für Empfehlungssysteme vorschlägt, Der Kern dieses Papiers war Darstellung des Empfehlungsprozesses in Bezug auf MDP, dh Zustände, Aktionen, Übergangswahrscheinlichkeiten, Belohnungsfunktion und so weiter.

Wenn wir der Einfachheit halber ein Einzelbenutzersystem annehmen, dann sehen Zustände wie k-Tupel (x1, x2, .. , xk) aus, wobei letztes Element xk das allerletzte Element darstellt, das vom Benutzer gekauft wurde. Angenommen, unser aktueller Status ist (x1, x2, x3), was bedeutet, dass der Benutzer x1, dann x2 und dann x3 in chronologischer Reihenfolge gekauft hat. Wenn er jetzt x4 kauft, wird der neue Zustand (x2, x3, x4) sein.

Nun, was das Papier vorschlägt, ist, dass diese Zustandsübergänge durch Aktionen ausgelöst werden, bei denen die Aktion "dem Benutzer ein Element x_i empfiehlt". aber das Problem ist, dass eine solche Aktion zu mehr als einem Staat führen kann.

Zum Beispiel, wenn unser aktueller Stand (x1, x2, x3) ist, und Handeln ist für den Benutzer „x4 empfehlen“, dann ist das mögliche Ergebnis könnte ein von zwei sein:

der Benutzer die Empfehlung von x4 akzeptiert und neuem Zustand wird (x2, x3, x4)
der Benutzer die Empfehlung von x4 ignoriert (dh kauft etwas anderes) und neuen Zustand wird jeder Staat (x2, x3, xi) wo xi sein! = ist x4

Meine Frage, hat MDP tatsächlich gleiche Aktion unterstützen Auslösung zwei oder mehr verschiedene Zustände ?

UPDATE. Ich denke, die Aktionen sollten formuliert werden als "bekommt Empfehlung von Artikel x_i und akzeptiert es" und "erhält Empfehlung von Artikel x_i und lehnt es ab" und nicht einfach "erhält Empfehlung von Artikel x_i"

Answer 1

Basiert auf this Wikipedia article, ja, es tut.

Ich bin kein Experte zu diesem Thema, da ich nur das Konzept nachgeschlagen habe, aber es sieht so aus, als ob die Menge der Zustände und die Menge der Aktionen keine inhärente Beziehung haben. Somit können mehrere Zustände mit jeder Aktion verknüpft (oder nicht verknüpft) und umgekehrt werden. Daher kann eine Aktion zu zwei oder mehr verschiedenen Zuständen führen, und für jedes Ergebnis gibt es eine bestimmte Wahrscheinlichkeit.

Beachten Sie, dass Sie in Ihrem Beispiel möglicherweise eine Reihe aller möglichen Zustände haben müssen (was so aussieht, als könnte es unendlich sein). Weiter ... basierend auf dem, was ich lese, sollten Ihre Zustände vielleicht nicht die Vergangenheitsgeschichte aufzeichnen. Es scheint, als ob Sie Geschichte aufzeichnen könnten, indem Sie eine Aufzeichnung der Kette selbst führen - anstelle von (x1, x2, x3, xi) als Staat hätten Sie etwas mehr wie (x1) -> (x2) -> (x3) -> (xi) - vier Zustände, die durch Aktionen verbunden sind. (Entschuldigung wegen der Notation. Ich hoffe, dass das Konzept einen Sinn ergibt.) Auf diese Weise repräsentiert Ihr Zustand die Kaufentscheidung (und ist daher endlich).

Answer 2

Sicher, das heißt randomisierte Politik. Wenn Sie die Belohnung für eine bestimmte Politik bewerten möchten, müssen Sie die Erwartung über die Wahrscheinlichkeitsverteilung der randomisierten Aktionen berücksichtigen.

Die folgende Referenz könnte von Interesse sein: Puterman, Martin L. Markov Entscheidungsprozesse: diskrete stochastische dynamische Programmierung. John Wiley & Sons, 2014

Wenn ich mich richtig erinnere, ist es bewiesen, dass es eine deterministische Politik ist, die die optimale Belohnung für jeden MDP mit einem endlichen diskreten Zustandsraum und Handlungsraum (und möglicherweise einigen anderen Bedingungen) gibt .Obwohl es möglicherweise randomisierte Richtlinien gibt, die die gleiche Belohnung bieten, können wir uns auf die Suche in der Menge der deterministischen Richtlinien beschränken.