Inteligenţa Artificială studiază entităţile inteligente
Problema banditului cu n braţe
Yüklə 220,58 Kb.
|
- Bu səhifədəki naviqasiya:
- Exemple
- Învăţarea pe baza unei funcţii de utilitate
Problema banditului cu n braţe:Să considerăm următoarea problemă de învăţare: suntem puşi adesea în situaţia de a alege între n variante sau acţiuni. După fiecare acţiune primim o recompensă numerică aleasă dintr-o distribuţie de probabilitate staţionară care depinde de acţiunea selectată. Obiectivul este de a maximiza recompensa totală obţinută după o anumită perioadă de timp (de exemplu după 100 de acţiuni selectate). Fiecare selectare a acţiunii se numeşte joc. Fiecare acţiune are o recompensă acordată dacă acţiunea este selectată. Aceasta se numeşte valoarea acţiunii respective. Dacă s-ar cunoaşte valoarea fiecărei acţiuni problema banditului cu n braţe ar fi foarte uşor de rezolva. Dacă fiecare acţiune are asociată o anumită recompensă, atunci există o acţiune a cărei valoare a recompensei este cea mai mare. Selectarea acţiunii a cărei recompensă estimată este cea mai mare se numeşte metoda greedy. Dacă se selectează acţiunea care maximizează recompensa atunci se exploatează cunoştinţele obţinute despre valorile acţiunilor. dacă nu se selectează acest tip de acţiune spunem că se explorează. Exploatarea are avantajele ei dar explorarea ar putea produce un rezultat mai bun pe termen lung. De exemplu, să presupunem că valorile acţiunilor de tip greedy sunt cunoscute cu exactitate, în timp ce alte acţiuni sunt estimate ca fiind aproximativ la fel de bune cu o marjă de incertitudine. S-ar putea totuşi ca una dintre aceste acţiuni să fie chiar mai bună decât acţiunea aleasă de greedy, dar nu se ştie care. Dacă mai sunt destule jocuri de efectuat , atunci este bine să se aleagă explorarea acţiunilor care nu sunt de tip greedy pentru a descoperi care dintre acestea sunt mai bune Recompensa este mai mică pe termen scurt, în timpul explorării, dar pe termen lung, după ce au fost descoperite acţiunile mai bune acestea pot fi exploatate. Deoarece nu este posibil să exploatăm şi să explorăm cu un singur selector de acţiuni, apare un conflict între explorare şi exploatare. În cazuri practice, decizia de a explora sau exploata depinde de valorile precise ale estimărilor, de incertitudini şi de numărul de jocuri rămase de jucat. Sunt mai multe metode de combinare a exploatării cu explorarea pentru formulări particulare ale problemei banditului cu n braţe şi ale problemelor înrudite cu aceasta.
În învăţarea pasivă, mediul generează stări de tranziţie şi agentul primeşte percepţii despre ele. Să considerăm un agent care încearcă să înveţe o funcţie de utilitate din stările descrise în figura 3.2.1.a). Să presupunem că agentul primeşte un model Mi, j care îi dă probabilitatea de tranziţie din starea i în starea j. În fiecare secvenţă de antrenament, agentul începe de la starea (1, 1) şi trece prin mai multe stări de tranziţie până când ajunge la una dintre cele două stări terminale (4, 2) sau (4, 3), stări în care agentul primeşte recompense. În figura 3.2.1.b) sunt date utilităţile fiecărei stări. Un set tipic de secvenţe de antrenament este următorul: (1, 1)(1, 2)(1, 3)(1, 2)(1, 3)(1, 2)(1, 1)(2, 1)(3, 1)(4, 1)(4, 2) şi recompensa – 1 (1, 1)(1, 2)(1, 3)(2, 3)(3, 3)(4, 3) şi recompensa +1 (1, 1)(1, 2)(1, 1)(1, 2)(1, 1)(2, 1)(3, 1) (3, 2) (4, 2) şi recompensa – 1 (1, 1)(1, 2)(1, 1)(1, 2)(1, 3)(2, 3)(1, 3)(2, 3)(3, 3)(4, 3)şi recompensa +1 (1, 1)(2, 1)(3, 1)(2, 1)(1, 1)(1, 2)(1, 3)(2, 3)(3, 3)(4, 3) şi recompensa +1 (1, 1)(2, 1)(1, 1)(1, 2)(1, 3)(2, 3)(3, 3)(3, 2)(4, 2) şi recompensa – 1
Figura 3.2.1. Scopul este de a utiliza informaţia despre recompense pentru a învăţa funcţia de utilitate U(i) asociată cu fiecare stare neterminală i. Voi considera că utilitatea unei secvenţe este suma recompenselor acumulate din stările secvenţei. Se numeşte recompensa de drum a unei stări suma recompenselor de la acea stare până la o stare terminală. Proiectarea unui agent pentru învăţarea prin întărire pasivă este descris în figura 3.2.1.c). Agentul păstrează o estimare U a utilităţilor stărilor, un tabel N în care se contorizează de câte ori s-a trecut printr-o anumită stare, şi o tabelă M a probabilităţilor de tranziţie dintr-o stare în alta. Presupun că fiecare percepţie e este suficientă pentru a determina o STARE (care este accesibilă), agentul poate determina recompensa unei percepţii, şi poate spune de asemenea dacă o anumită stare este TERMINALĂ. În general, un agent poate să-şi reactualizeze utilitatea curentă după fiecare observaţie. Ideea care stă la baza învăţării prin întărire este algoritmul pentru reactualizarea valorilor utilităţii date în secvenţa de antrenament. function Agent_Pasiv(e) returns acţiune static: U // tabela utilităţilor estimate N //tabela frecvenţei stărilor M //tabela probabilităţilor de tranziţie dintr-o stare în alta percepţii //secvenţa de percepţii (iniţial vidă) adaugă e la percepţii Incrementează N[STARE[e]] U := Reactualizează(U, e, percepţii, M, N) if Terminală(e) then percepţii := secvenţa vidă return acţiunea Observă
Fig 3.2.1.c) scheletul unui agent care foloseşte învăţarea prin întărire pasivă Agentul descris în figura 3.2.1.c) doar observă mediul în care se află şi încearcă să înveţe utilitatea U a fiecărei stări. De asemenea agentul urmăreşte frecvenţa tranziţiilor printr-o anumită stare şi probabilităţilor de atingere a unei anumite stări.
|
