Pembelajaran Penguatan: Suatu Pengantar. Edisi kedua, dalam proses ., Richard S. Sutton dan Andrew G. Barto (c) 2012, hlm. 67-68.
Memecahkan tugas pembelajaran penguatan berarti, secara kasar, menemukan kebijakan yang mencapai banyak penghargaan dalam jangka panjang. Untuk MDP terbatas, kita dapat dengan tepat menetapkan kebijakan optimal dengan cara berikut. Fungsi nilai menentukan pemesanan sebagian atas kebijakan. Sebuah kebijakan didefinisikan untuk menjadi lebih baik dari atau sama dengan kebijakan jika pengembalian yang diharapkan lebih besar dari atau sama dengan yang , untuk semua negara. Dengan kata lain, jika dan hanya jika , untuk semua . Selalu ada setidaknya satu kebijakan yang lebih baik atau sama dengan semua kebijakan lainnya. Ini adalah kebijakan yang optimal.
Mengapa selalu ada setidaknya satu kebijakan yang lebih baik atau sama dengan semua kebijakan lainnya?
Jawaban:
Hanya melewati bagian yang dikutip, paragraf yang sama sebenarnya memberi tahu Anda apa kebijakan ini: itu adalah yang mengambil tindakan terbaik di setiap negara. Dalam MDP, tindakan yang kami lakukan di satu negara tidak memengaruhi hadiah untuk tindakan yang dilakukan di negara lain, jadi kami hanya dapat memaksimalkan kebijakan negara bagian demi negara.
sumber
Keberadaan kebijakan yang optimal tidak jelas. Untuk mengetahui alasannya, perhatikan bahwa fungsi nilai hanya menyediakan pemesanan parsial atas ruang kebijakan. Ini berarti:
Karena ini hanya pemesanan parsial, mungkin ada kasus di mana dua kebijakan, dan π 2 , tidak dapat dibandingkan. Dengan kata lain, ada himpunan bagian dari ruang keadaan, S 1 dan S 2 sedemikian rupa sehingga:π1 π2 S1 S2
Dalam hal ini, kami tidak dapat mengatakan bahwa satu kebijakan lebih baik daripada yang lain. Tetapi jika kita berurusan dengan MDP terbatas dengan fungsi nilai terikat, maka skenario seperti itu tidak pernah terjadi. Hanya ada satu fungsi nilai optimal, meskipun mungkin ada beberapa kebijakan optimal.
Untuk bukti ini, Anda perlu memahami teorema Titik Tetap Banach. Untuk analisis terperinci, silakan merujuk .
sumber
Pengaturan
Kami sedang mempertimbangkan dalam pengaturan:
The kebijakan yang optimal didefinisikan sebagai: dan fungsi nilai optimal adalah: V * = max π V π ( s ) , ∀ s ∈ S Ada dapat satu set kebijakan yang mencapai maksimum. Tetapi hanya ada satu fungsi nilai optimal: V ∗ = V π ∗
Pertanyaan
How to prove that there exists at least oneπ∗ which satisfies (1) simultaneously for all s∈S ?
Outline of proof
Construct the optimal equation to be used as a temporary surrogate definition of optimal value function, which we will prove in step 2 that it is equivalent to the definition via Eq.(2).
Turunkan persamaan dari fungsi nilai optimal mendefinisikan melalui Persamaan (4) dan melalui Persamaan (2).
(Catat sebenarnya kita hanya perlu arah keperluan dalam buktinya, karena kecukupan sudah jelas karena kita membangun Persamaan. (4) dari Persamaan. (2).)
Buktikan bahwa ada solusi unik untuk Persamaan. (4).
Pada langkah 2, kita tahu bahwa solusi yang diperoleh pada langkah 3 juga merupakan solusi untuk Persamaan. (2), jadi ini adalah fungsi nilai yang optimal.
Dari fungsi nilai optimal, kita dapat memulihkan kebijakan optimal dengan memilih tindakan maximizer dalam Persamaan (4) untuk setiap negara.
Detail langkah-langkahnya
1V∗(s)=Vπ∗(s)=Ea[Qπ∗(s,a)] Vπ∗(s)≤maxa∈AQπ∗(s,a) s~ such that Vπ∗≠maxa∈AQπ∗(s,a) , we can choose a better policy by maximizing Q∗(s,a)=Qπ∗(s,a) over a .
2(=>)
Follows by step 1.
(<=)
i.e. IfV~ satisfies V~(s)=maxa∈A[R(s,a)+γ∑s′∈ST(s,a,s′)V~(s′)] , then V~(s)=V∗(s)=maxπVπ(s),∀s∈S .
Define the optimal Bellman operator as
a) IfV~≥TV~ , then V~≥V∗ .
b) IfV~≤TV~ , then V~≤V∗ .
Proof:
a)
For anyπ=(d1,d2,...) ,
By induction, for anyn ,
Since
Follows from step 1.
3The optimal Bellman operator is a contraction inL∞ norm, cf. [2].
Proof: For anys ,
Thus by Banach fixed point theorum it follows thatT has a unique fixed point.
References
[1] Puterman, Martin L.. “Markov Decision Processes : Discrete Stochastic Dynamic Programming.” (2016).
[2] A. Lazaric. http://researchers.lille.inria.fr/~lazaric/Webpage/MVA-RL_Course14_files/slides-lecture-02-handout.pdf
sumber
The policya=π(s) gives the best action a to execute in state s according to policy π , i.e. the value function vπ(s)=maxa∈Aqπ(s,a) is highest for action a in state s .
Thus there is always a policyπ∗ which gives equal or higher expected rewards than policy π . Note that this implies that π could be an/the optimal policy (π∗ ) itself.
sumber