基于強(qiáng)化學(xué)習(xí)的值迭代算法

崔軍曉等

摘要：強(qiáng)化學(xué)習(xí)（Reinforcement Learning）是學(xué)習(xí)環(huán)境狀態(tài)到動作的一種映射，并且能夠獲得最大的獎賞信號。強(qiáng)化學(xué)習(xí)中有三種方法可以實(shí)現(xiàn)回報的最大化：值迭代、策略迭代、策略搜索。該文介紹了強(qiáng)化學(xué)習(xí)的原理、算法，并對有環(huán)境模型和無環(huán)境模型的離散空間值迭代算法進(jìn)行研究，并且把該算法用于固定起點(diǎn)和隨機(jī)起點(diǎn)的格子世界問題。實(shí)驗(yàn)結(jié)果表明，相比策略迭代算法，該算法收斂速度快，實(shí)驗(yàn)精度好。

關(guān)鍵詞：強(qiáng)化學(xué)習(xí)；值迭代；格子世界

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）31-7348-03

Abstract： Reinforcement learning is learning how to map situations to actions and get the maximize reward signal. In reinforcement learning， there are three methods that can maximize the cumulative reward. They are value iteration， policy iteration and policy search. In this paper， we survey the foundation and algorithms of reinforcement learning ， research about model-based value iteration and model-free value iteration and use this algorithms to solve the fixed starting point and random fixed starting point Gridworld problem. Experimental result on Gridworld show that the algorithm has faster convergence rate and better convergence performance than policy iteration.

Key words： reinforcement learning； value Iteration；Gridworld

強(qiáng)化學(xué)習(xí)可以解決自動控制，人工智能，運(yùn)籌學(xué)等領(lǐng)域方面的各種問題。其中自動控制和人工智能是強(qiáng)化學(xué)習(xí)的重要發(fā)源地。在自動控制領(lǐng)域中，強(qiáng)化學(xué)習(xí)用于自適應(yīng)的最優(yōu)控制問題。在人工智能領(lǐng)域中，強(qiáng)化學(xué)習(xí)用于協(xié)助構(gòu)建人工agent，可以在未被構(gòu)建的未知環(huán)境中找到最優(yōu)化的行為。

我們在這里對強(qiáng)化學(xué)習(xí)的值迭代算法進(jìn)行研究，并以格子世界為例將該算法進(jìn)行實(shí)際運(yùn)用，以此表現(xiàn)出該算法的優(yōu)勢。

如圖 1所示，agent做出了一個動作，環(huán)境對agent做出的動作產(chǎn)生回應(yīng)，從而改變了agent的狀態(tài)并且對agent給出一定的獎賞。在每個時間步中，agent都要實(shí)現(xiàn)從狀態(tài)到每一個可能選到的動作的映射。這個映射就是agent的策略。

3 離散空間實(shí)驗(yàn)結(jié)果分析

現(xiàn)在來用基于模型的值迭代算法解決格子世界問題。將算法1直接運(yùn)用在格子世界問題上。設(shè)定初始狀態(tài)的狀態(tài)值函數(shù)全部為0，折扣因子[γ]為0.5。對應(yīng)的值迭代結(jié)果如圖3所示，策略如圖4所示。

圖3每一步迭代的策略由圖4表示，同時也是策略改進(jìn)圖像。根據(jù)值函數(shù)估計值得到的貪心策略的序列。箭頭表示該狀態(tài)中能取得最大值的動作。通過圖4可得第五輪迭代和第六輪迭代的策略已經(jīng)相同，此時策略為最優(yōu)策略。

[V6]，[V7]時所有狀態(tài)的值函數(shù)均已經(jīng)相同，可以認(rèn)為已經(jīng)收斂。從圖4可以得出經(jīng)過多次迭代，策略從無序到有序，最終達(dá)到最優(yōu)策略，通過值迭代得到的最終策略是正確的。

4 小結(jié)

本文簡易介紹了強(qiáng)化學(xué)習(xí)基本概念，并說明如何使用強(qiáng)化學(xué)習(xí)值迭代方法在離散空間中找到最優(yōu)策略。在離散空間中，若模型已知，可以使用動態(tài)規(guī)劃的方法，通過策略評估和策略改進(jìn)的迭代求出值函數(shù)和最優(yōu)策略。策略評估和策略改進(jìn)的迭代方式不同可以將動態(tài)規(guī)劃分為值迭代和策略迭代。該文通過格子世界的實(shí)驗(yàn)，驗(yàn)證了值迭代的高效收斂性，彌補(bǔ)了策略迭代的不足。

參考文獻(xiàn)：

[1] Barto A G.Reinforcement learning： An introduction[M].MIT press，1998.

[2] Busoniu L，Babuska R，De Schutter B，et al.Reinforcement learning and dynamic programming using function approximators[M].CRC Press，2010.

[3] Singh S， Jaakkola T，Littman M L，et al.Convergence results for single-step on-policy reinforcement-learning algorithms[J].Machine Learning，2000，38（3）：287-308.

[4] Boyan J A.Technical update： Least-squares temporal difference learning[J].Machine Learning，2002，49（2-3）：233-246.

[5] Singh S P，Sutton R S.Reinforcement learning with replacing eligibility traces[J].Machine learning， 1996，22（1-3）： 123-158.

[6] Barto A G，Sutton R S，Watkins C J C H.Learning and sequential decision making [M]//Gabriel M，Moore J W.Learning and computational neuroscience： Foundations of adaptive networks.Cambridge，MA：MIT Press， 1989.

[7] 陳浩.基于強(qiáng)化學(xué)習(xí)的蟻群聚類研究及應(yīng)用[D].蘇州：蘇州大學(xué)， 2011.

[8] 高陽，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動化學(xué)報，2004， 30（1）： 86-100.