マルコフ決定プロセス：異なる状態につながる同じアクション

Question

先週私は推奨システムの代替ソリューションとしてMDPを提案する論文を読んだ。 この論文の中心は、MDP、すなわち州、行動、遷移確率、報酬関数などを含む。

シンプルさを単一ユーザシステムと仮定すると、状態はkタプル(x1, x2, .. , xk)のように見えます。ここで、最後の要素xkは、ユーザが購入した最後の項目を表します。 たとえば、現在の状態が(x1, x2, x3)であるとします。つまり、x1を購入した後、x2、x3を購入したことを意味します。今すぐx4を購入すると、新しい状態は(x2, x3, x4)になります。

ここでは、これらの状態遷移はアクションによってトリガされ、アクションは「アイテムx_iをユーザに推薦する」ことを示しています。問題はそのようなアクションが複数の状態につながる可能性があることです。例えば

私たちの現在の状態が(x1, x2, x3)あり、そしてアクションは、ユーザーに「X4をお勧めします」であれば、可能な結果は、2つのうちいずれかである可能性があります

ユーザーがX4の勧告、および新しい状態を受け入れユーザーがX4の勧告を無視し(x2, x3, x4)
になります（つまり、何か他のものを買う）と新しい状態が(x2, x3, xi)どこXI！= X4

私の質問があり、MDPは、実際に二つ以上の異なるがトリガー同じアクションをサポートしていますどのような状態になります状態？

更新。 「アイテムx_iの推薦を得て、それを拒否し、アイテムx_iの推薦を得て、それを拒否する」というだけで、アクションは「アイテムx_iの推薦を受け取り、それを拒否する」として策定されるべきだと考える。

Answer 1

this Wikipedia articleに基づき、そうです。

私はただ概念を調べただけですが、状態のセットと一連のアクションには本質的な関係がないように見えます。したがって、複数の状態を任意のアクション（リンクされていない）にリンクすることができ、その逆も可能です。したがって、アクションは2つ以上の異なる状態につながり、各結果に対して特定の確率が存在します。

あなたの例では、すべての可能な状態（無限になる可能性があるように見える）のセットを持つ必要があることに注意してください。さらに....私が読んでいることに基づいて、あなたの州は過去の歴史を記録すべきではないでしょう。状態として(x1, x2, x3, xi)ではなく、(x1) -> (x2) -> (x3) -> (xi) - アクションによってリンクされた4つの状態のようなものを持っているでしょう。 （表記については申し訳ありませんが、そのコンセプトが意味をなされることを願っています。）このように、あなたの国は購入の選択を表します（したがって、有限です）。

Answer 2

確かに、これはランダム化ポリシーと呼ばれます。特定のポリシーの報酬を評価したい場合は、ランダム化されたアクションの確率分布に期待する必要があります。

以下の参考文献は興味深いかもしれません。Puterman、Martin L. Markov決定プロセス：離散確率的動的プログラミング。ジョン・ワイリー&サンズ、2014年

私の記憶が正しければ、有限離散状態空間と行動空間を持つ任意のMDPに最適な報酬（そしておそらく他のいくつかの条件）を与える決定論的政策があることが証明されました。同じ報酬を与える無作為化されたポリシーがあるかもしれないが、決定論的なポリシーのセットで検索することに制限することができる。