Reinforcement Learning：An Introduction NOTE[5]
1.5 拓展例子：井字棋
為了說明強化學習的一般概念，并與其他方法進行對比，我們接下來将更詳細地考慮一個示例。
想想我們熟悉的孩子玩的井字棋。棋手在三行三列的棋盤上博弈，一個棋手下X，另一個下O。若X或O的連續三個棋子落于一行或一列或同一斜線上則獲勝；若棋盤被填滿也不能決出勝負則為平局。讓我們假設，我們是在和一個不完美的棋手比賽，他的戰術有時是不正确的，并且允許我們獲勝。而且，讓我們考慮平局和虧損對我們同樣不利。我們如何建構一個能在對手的遊戲中發現玩家的漏洞，并取得最大化獲勝的機會的機器棋手？
雖然這是一個簡單的問題，但傳統方法難以很好地解決。例如，博弈論中經典的“極小極大”解在這裡是不正确的，因為對手可能有特殊的博弈方式。極小極大棋手從不去他可能輸棋的局面，就是由于對手的失誤他可能能勝出（For example, a minimax player would never reach a game state from which it could lose, even if in fact it always won from that state because of incorrect play by the opponent）。經典的連續決策問題的最優方法，如動态規劃，可以計算出任何對手的最優解，但要求輸入該對手的全部規格，包括對手在每個基礎狀态（board state，不明白）下移動的機率。讓我們假設在問題無法獲得這些先驗資訊，因為它不适用于大多數實際問題。另一方面，這樣的資訊可以從經驗中估計，在這個例子上就是和對手下棋。最好能學習對手的行為模式，達到一定的置信水準（some level of confidence），然後應用動态規劃來計算近似的對手模型的最優解。這與我們在本書後面研究的強化學習方法沒有什麼不同。
這個問題的一種進化方法将直接搜尋一個政策空間以找到最可能赢的那個。在這裡，一個政策是告訴玩家在遊戲中的各個狀态下如何進行移動的規則–既3*3的闆子上x和o所有可能擺放的位置。我們考慮政策中，獲勝的估計機率将通過與對手進行一些比賽來獲得。這一評估将決定下一步将考慮哪個或哪些政策。一種典型的演化方法是在政策空間中進行爬坡，然後在嘗試進步的過程中依次生成和評估政策。或者，也許可以使用遺傳算法來維護和評估一組政策。實際上，我們有上百種不同的優化方法。
下面是使用值函數的方法來解決黑白棋問題的方法。首先，我們建立了一個數字表，每個數字對應一個遊戲狀态。每一個數字将是我們獲勝的最新估計。我們把這個估計看作是狀态的價值，整個表是學習的值函數。如果A的勝率高于B，我們就認為A的價值高于B，或A比B更好。假設我們玩X，那麼所有三個X居于一列的獲勝的機率是1，因為我們已經赢了。同樣地，對于所有三個O居于一列，或者所有三列被“填充”（or that are “filled up），獲勝的機率是0，因為從那時起我們就不可能赢了。我們将所有其他狀态的初始值設為0.5，表示猜測我們有50%的獲勝機會。
我們和對手打了許多場比賽。為了選擇我們的動作，我們檢查每個動作可能産生的狀态（在棋盤上的每個空格中有一個），并在表中查找它們目前的值(上一段的價值)。大多數時候，我們貪婪地移動，選擇最有價值的運動，也就是說，以最高的獲勝機率。然而，偶爾我們會從其他動作中随機選擇。這些被稱為探索性的行動，因為它們使我們體驗到我們可能從未見過的狀态。在遊戲中移動和考慮的序列可繪制成圖1.1。
圖1.1：一系列井字棋移動。實線表示遊戲中所采取的動作；虛線表示我們（強化學習播放器）考慮但未做的動作。我們的第二次移動是一個探索性的舉措，這意味着e*所表示的移動在等級上優于目前舉動。探索性的動作不會導緻任何學習，但我們的其他動作都會産生更新，導緻了如弧線箭頭所顯示的那種更新–如文中所寫，估計值自下而上的産生了變化。
Figure 1.1: A sequence of tic-tac-toe moves. The solid lines represent the moves taken during a game; the
dashed lines represent moves that we (our reinforcement learning player) considered but did not make. Our
second move was an exploratory move, meaning that it was taken even though another sibling move, the one
leading to e, was ranked higher. Exploratory moves do not result in any learning, but each of our other moves
does, causing updates as suggested by the curved arrow in which estimated values are moved up the tree from
later nodes to earlier as detailed in the text.
當我們下棋的時候，遊戲中根據狀态不斷改變值，使這些值能更準确地估計獲勝的可能性。為了做到這一點，在貪婪移動後，我們重寫前一狀态的值（we “back up” the value of the state after each greedy move to the state before the move）。更準确地說，前一狀态的目前值被更新以接近後續狀态的值。這可以通過将前一狀态值稍向後狀态值靠近一小部分來完成（This can be done by moving the earlier state’s value a fraction of the way toward the value of the later state）。如果讓s表示在移動前的狀态，s‘表示移動後狀态，那麼将s的估計值的更新表示為V（s），可以寫成
Python 通過簡單的強化學習實作井字棋（Tic-Tac-Toe）
https://blog.csdn.net/JerryLife/article/details/81385766
其中x是一個小的正分數，稱為步長參數，它影響學習速度。
此更新規則是時間差學習方法的一個示例，之是以這麼稱呼它，是因為它的更改是基于兩個不同時間估計值之間的差異V (s0) - V (s)。
上面描述的方法在這項任務中表現得很好。
例如，如果步長參數随時間适當減小，那麼對于任何固定的對手，該方法将收斂于我們的玩家給定的每個狀态下獲勝的真實機率。
此外，所采取的行動(除了探索性的行動)實際上是針對這個(不完美的)對手的最佳行動。
換句話說，該方法收斂于與該對手進行博弈的最優政策。
如果步長參數沒有随時間減少到0，那麼這個玩家在面對慢慢改變遊戲方式的對手時也能玩得很好。
這個例子說明了演化方法和學習值函數的方法之間的差異。為了評估一個政策，進化方法持有政策盒并與對手進行多次博弈，或者使用對手的模型模拟多次博弈。獲勝的頻率給出了該政策獲勝機率的無偏估計，并可用于指導下一個政策選擇。但是每個政策更改隻在許多遊戲之後進行，并且隻使用每個遊戲的最後總結果:忽略了遊戲期間發生的事情。例如，如果玩家赢了，那麼它在遊戲中的所有行為都将得到獎勵，independently of how specic moves might have been critical to the win.甚至連從未發生過的動作也會受到贊揚! 相反，值函數方法允許對各個狀态進行評估。最後，演化方法和價值函數方法都是對政策空間的搜尋，而價值函數的學習利用的是博弈過程中的資訊。
這個簡單的例子說明了強化學習方法的一些關鍵特征。首先，在與環境互動的過程中，重點是學習，在這裡是與對手的互動。第二，有一個明确的目标，正确的行為需要計劃或遠見，考慮到一個人的選擇延遲的影響。例如，簡單的強化學習玩家将學會為目光短淺的對手設定多步陷阱。強化學習解決方案的一個顯著特點是，它可以實作規劃和向前看的效果，而不需要使用對手的模型，也不需要對未來狀态和動作的可能序列進行顯式搜尋。
雖然這個例子說明了強化學習的一些關鍵特征，但它太簡單了，可能會給人一種強化學習比實際更有限的印象。雖然三棋是兩人遊戲，但強化學習也适用于沒有外部對手的情況，也就是說，在與自然對抗的情況下。”強化學習也不局限于将行為分解為單獨的章節的問題，就像三子棋的單獨遊戲，隻有在每一章節的結尾才有獎勵。它同樣适用于行為不确定持續的情況，以及在任意時候得到不同數額的獎勵的情況。強化學習也适用于那些甚至不能分解成離散時間步長的問題，比如井字遊戲。一般原則也适用于連續時間問題，盡管理論變得更加複雜，我們在這個介紹性的進行中省略了它。（畢竟基本架構是MDP，能分狀态就行）
井字遊戲有一個相對較小的有限狀态集，而強化學習可以在狀态集非常大，甚至無限時使用。例如，Gerry Tesauro(1992,1995)将上述算法與人工神經網絡相結合，學習下約有1020種狀态的西洋雙陸棋。有了這麼多的狀态，我們不可能體驗到比其中一小部分更多的狀态。Tesauro的程式比以前的任何程式都玩得好得多，現在的水準已經達到了世界上最好的人類玩家的水準(參見第16章)。神經網絡為程式提供了從經驗中歸納的能力，是以，在新的狀态下，它根據從過去面臨的類似狀态中儲存的資訊(由其網絡決定)來選擇移動。強化學習系統處理如此大的狀态集問題的能力與它從過去經驗中總結出的恰當程度密切相關。正是在這種情況下，我們最需要監督學習方法和強化學習。神經網絡和深度學習章節9.6)不是唯一的，或者不一定是最好的方法。
在這個井字遊戲的例子中，學習一開始并沒有超越遊戲規則的先驗知識，但是強化學習絕不是學習和智力的白闆。相反，先驗資訊可以通過多種方式被整合到強化學習中，這對有效學習至關重要。在井字遊戲的例子中，我們也獲得了真實的狀态，而強化學習也可以應用于部分狀态被隐藏的時候，或者當不同的狀态在學習者看來是相同的時候。
最後，井字遊戲者能夠向前看并知道每一個可能的移動會産生的狀态。要做到這一點，它必須有一個遊戲模型，讓它能夠“思考”自己的環境将如何變化，以應對自己可能永遠不會采取的行動。許多問題都是這樣，但在另一些問題中，甚至缺乏行動效果的短期模型。強化學習可以應用于任何一種情況。不需要模型，但是如果模型可用或可以學習，就可以很容易地使用它們(第8章)。
另一方面，有些強化學習方法根本不需要任何環境模型。無模型系統甚至不能考慮它們的環境将如何響應單個操作而改變。從這個意義上說，井字遊戲的玩家是無模式的:它沒有任何對手的模式。因為模型必須相當精确。當解決問題的真正瓶頸是難以建立足夠精确的環境模型時，有用的、無模型的方法比更複雜的方法具有優勢。無模型方法也是基于模型方法的重要構件。在本書中，在讨論如何将它們作為更複雜的基于模型的方法的元件之前，我們将用幾個章節來讨論無模型方法。
強化學習可以用于系統的高水準和低水準。盡管井字遊戲玩家隻學習了遊戲的基本動作，但沒有什麼能阻止強化學習在更高層次上工作，因為在更高層次上，每一個“動作”本身都可能是一個複雜的問題解決方法的應用。在分層學習系統中，強化學習可以在多個層次上同時進行。
練習1.1:自我遊戲假設，上述的強化學習算法不是與随機的對手進行遊戲，而是與自己進行遊戲，雙方都進行學習。你認為在這種情況下會發生什麼?它會學習不同的招數選擇政策嗎?
1.一開始學習會變慢，但是會比固定玩家對手的情況下學習到更多招數，
最後收斂速度會變慢，也許不會收斂
2.會的
練習1.2:對稱性 許多井字遊戲的位置看起來不同，但因為對稱性而實際上是相同的。我們如何修改上述學習過程以利用這一點呢?這種改變會在哪些方面改善學習過程?現在再想想。假設對手沒有利用對稱性。那樣的話，我們應該嗎?那麼，對稱等價的位置必然具有相同的值，這是真的嗎?
練習1.3:貪心遊戲假設 強化學習遊戲者是貪心的，也就是說，他總是會走到他認為最好的位置。它會比一個不貪心的玩家玩得更好，還是更差?可能會出現什麼問題?
練習1.4:從Exploration學習 :假設所有的動作(包括探索性的動作)之後都發生了學習更新。如果随時間适當減少步長參數(但不減少探索的趨勢)，則狀态值将收斂于一組機率。當我們做的時候，和我們不做的時候，從探索性的動作中得到的兩組機率是什麼?假設我們繼續探索，哪一組機率可能更好學?哪一個會帶來更多的勝利?
練習1.5:其他改進你能想到其他方法來改進強化學習玩家嗎?你能想出更好的辦法來解決所提出的井字遊戲問題嗎?