Mengapa selalu ada setidaknya satu kebijakan yang lebih baik atau sama dengan semua kebijakan lainnya?

14

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 vπ(s)vπ(s) , untuk semua sS . 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?

sh1ng
sumber
Bukti yang sangat rinci (yang menggunakan teorema titik tetap Banach) muncul di bab 6.2 dari "Proses Keputusan Markov" oleh Puterman.
Toghs

Jawaban:

3

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.

Don Reba
sumber
Bukankah jawaban ini sepenuhnya salah? Bagaimana Anda bisa mengatakan bahwa mengoptimalkan kebijakan negara demi negara mengarah ke kebijakan optimal. Jika saya mengoptimalkan lebih dari keadaan dan saya butuh S t + 1 dan kemudian mengoptimalkan di S t + 1 mengarah ke fungsi nilai optimal V t + 1 tetapi ada kebijakan lain di mana S t mengarah secara optimal ke S l dan optimal fungsi nilai S l lebih tinggi dari V t + 1 . Bagaimana Anda bisa mengesampingkan ini dengan analisis sepintas seperti itu?StSt+1St+1Vt+1StSlSlVt+1
MiloMinderbinder
@MiloMinderbinder Jika kebijakan optimal pada adalah memilih S t + 1 , maka nilai S t + 1 lebih tinggi dari nilai S l . StSt+1St+1Sl
Don Reba
Salahku. Typo dikoreksi: 'Apakah jawaban ini tidak sepenuhnya salah? Bagaimana Anda bisa mengatakan bahwa mengoptimalkan kebijakan negara demi negara mengarah ke kebijakan optimal? Jika saya mengoptimalkan lebih dari keadaan dan itu membawa saya ke S t + 1 dan kemudian mengoptimalkan di S t + 1 mengarah ke fungsi nilai yang optimal V t + 2 dari S t + 2 tetapi ada kebijakan lain di mana S t meskipun mengarah suboptimally ke S l + 1 dan karenanya fungsi nilai dari S t + 1StSt+1St+1Vt+2St+2StSl+1St+1 lebih tinggi dari Vl+1 tapi fungsi nilai lebih tinggi berdasarkan kebijakan ini daripada di bawah kebijakan yang ditemukan dengan mengoptimalkan negara oleh negara. Bagaimana ini dikalahkan oleh Anda? ' St+2
MiloMinderbinder
Saya pikir definisi akan mencegah hal ini terjadi sejak awal, karena harus memperhitungkan pengembalian di masa depan juga. V
Flying_Banana
Pertanyaannya kemudian adalah: mengapa ada? Anda tidak dapat menyiasati Teorema Titik Tetap Banach :-)q
Fabian Werner
10

Keberadaan kebijakan yang optimal tidak jelas. Untuk mengetahui alasannya, perhatikan bahwa fungsi nilai hanya menyediakan pemesanan parsial atas ruang kebijakan. Ini berarti:

ππvπ(s)vπ(s),sS

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π2S1S2

vπ(s)vπ(s),sS1

vπ(s)vπ(s),sS2

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 .

Karthik Thiagarajan
sumber
7

Pengaturan

Kami sedang mempertimbangkan dalam pengaturan:

  • Tindakan terpisah
  • Status diskrit
  • Hadiah terbatas
  • Kebijakan stasioner
  • Cakrawala tak terbatas

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 π

(1)πargmaxπVπ(s),sS
(2)V=maxπVπ(s),sS
(3)V=Vπ

Pertanyaan

How to prove that there exists at least one π which satisfies (1) simultaneously for all sS ?

Outline of proof

  1. 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).

    (4)V(s)=maxaA[R(s,a)+γsST(s,a,s)V(s)]
  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).)

  3. Buktikan bahwa ada solusi unik untuk Persamaan. (4).

  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.

  5. Dari fungsi nilai optimal, kita dapat memulihkan kebijakan optimal dengan memilih tindakan maximizer dalam Persamaan (4) untuk setiap negara.

Detail langkah-langkahnya

1

V(s)=Vπ(s)=Ea[Qπ(s,a)]Vπ(s)maxaAQπ(s,a)s~ such that VπmaxaAQπ(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. If V~ satisfies V~(s)=maxaA[R(s,a)+γsST(s,a,s)V~(s)], then V~(s)=V(s)=maxπVπ(s),sS.

Define the optimal Bellman operator as

(5)TV(s)=maxaA[R(s,a)+γsST(s,a,s)V(s)]
So our goal is to prove that if V~=TV~, then V~=V. We show this by combining two results, following Puterman[1]:

a) If V~TV~, then V~V.

b) If V~TV~, then V~V.

Proof:

a)

For any π=(d1,d2,...),

V~TV~=maxd[Rd+γPdV~]Rd1+γPd1V~
Here d is the decision rule(action profile at specific time), Rd is the vector representation of immediate reward induced from d and Pd is transition matrix induced from d.

By induction, for any n,

V~Rd1+i=1n1γiPπiRdi+1+γnPπnV~
where Pπj represents the j-step transition matrix under π.

Since

Vπ=Rd1+i=1γiPπiRdi+1
we have
V~VπγnPπnV~i=nγiPπiRdi+10 as n
So we have V~Vπ. And since this holds for any π, we conclude that
V~maxπVπ=V
b)

Follows from step 1.

3

The optimal Bellman operator is a contraction in L norm, cf. [2].

Proof: For any s,

|TV1(s)TV2(s)|=|maxaA[R(s,a)+γsST(s,a,s)V1(s)]maxaA[R(s,a)+γsST(s,a,s)V(s)]|()|maxaA[γsST(s,a,s)(V1(s)V2(s))]|γV1V2
where in (*) we used the fact that
maxaf(a)maxag(a)maxa[f(a)g(a)]

Thus by Banach fixed point theorum it follows that T 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

LoveIris
sumber
-1

The policy a=π(s) gives the best action a to execute in state s according to policy π, i.e. the value function vπ(s)=maxaAqπ(s,a) is highest for action a in state s.

There is always at least one policy that is better than or equal to all other policies.

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.

agold
sumber
3
How does this answer the question? You're basically repeating statements written in the quote.
nbro