馬爾可夫決策過程：導致不同狀態的相同行動

Question

上週我讀過一篇文章，建議將MDP作爲推薦系統的替代解決方案， 該論文的核心是用MDP表示推薦過程，即州，行爲，轉換概率，獎勵功能等。

如果我們爲簡單起見假設單用戶系統，則狀態看起來像k元組(x1, x2, .. , xk)，其中最後一個元素xk表示用戶購買的最後一個項目。 例如，假設我們當前的狀態爲(x1, x2, x3)，這意味着用戶按時間順序購買x1，然後x2，然後x3。現在，如果他購買x4，新的狀態將是(x2, x3, x4)。

現在，文章提出的是，這些狀態轉換是由動作觸發的，其中動作是「向用戶推薦項目x_i」。但問題是這種行爲可能導致多個國家。

例如，如果我們目前的狀態是(x1, x2, x3)，並採取行動是「推薦×4」的用戶，那麼可能的結果是二分之一的：

用戶接受X4的建議，和新的狀態將(x2, x3, x4)
用戶忽略X4的建議（即買別的東西）和新的狀態將是任何狀態(x2, x3, xi)其中xi！= X4

我的問題是，是否MDP真正支持相同的動作觸發兩個或多個不同狀態 ？

UPDATE。我認爲這些行爲應該被形成爲「得到物品x_i的推薦並接受它」和「得到物品x_i的推薦並拒絕它」，而不是簡單地「得到物品x_i的推薦」

Answer 1

基於this Wikipedia article，是的，確實。

我不是這方面的專家，因爲我只是查了一下這個概念，但它看起來好像一組狀態和一組行爲沒有內在聯繫。因此，多個狀態可以鏈接到任何動作（或不鏈接），反之亦然。因此，一項行動可能會導致兩種或更多種不同的狀態，每種結果都會有一定的概率。

請注意，在您的示例中，您可能必須具有一組所有可能的狀態（看起來好像可能是無限的）。進一步......根據我正在閱讀的內容，你的國家可能不應該記錄過去的歷史。看起來好像您可以通過保留鏈條本身的記錄來記錄歷史記錄 - 而不是(x1, x2, x3, xi)作爲一種狀態，您可能更喜歡(x1) -> (x2) -> (x3) -> (xi) - 通過動作鏈接的四種狀態。 （抱歉，關於符號，我希望這個概念有意義。）這樣，你的狀態代表購買的選擇（因此是有限的）。

Answer 2

當然，這被稱爲隨機政策。如果您想評估某項政策的回報，則必須對隨機行動的概率分佈進行預測。

以下參考文獻可能是有意義的：Puterman，Martin L. Markov decision processes：discrete stochastic dynamic programming。約翰·威利父子& 2014年

如果我沒有記錯，它被證明是有確定性的政策，讓任何MDP的最優收益與有限離散狀態空間和行爲空間（可能還有一些其他條件） 。雖然可能有隨機政策給予相同的獎勵，但我們可以因此限制在確定性政策集合中進行搜索。