Email diskuse numerických nestabilit hazardního hráče problému


Original: http://webdocs.cs.ualberta.ca/~sutton/book/gamblers.html

Optimální podmínky uvedené na obrázku 4.6 není jedinečný. Existuje mnoho dalších optimální politiky, z nichž podíl optimální funkce také zobrazené na obrázku. Jaké optimální politika získáte od svého algoritmu hodnoty iterace závisí na tom, jak to zlomí vazby uvnitř numerického řešení vašeho počítače. (Daniel Loeb, Daniel Polani, Francesco Decomite, a mnozí studenti)

Následující e-mail úvahy o otázce, v chronologickém pořadí:

Datum: Po. 01.03.1999 12:45:33 +0100 (MEZ)
Od: Daniel Polani
Pro: [email protected]
Předmět: Dotaz Gambler je problém ve vaší knize RL

Vážení prof Sutton,

Byl jsem dávat kurzu na učení zesílení tuto zimu a
vyvstala zajímavá otázka ve spojení s hazardního hráče
problém ve své knize RL.

Tam byla nějaká diskuse v mém kurzu proč optimální politiky jako
je znázorněno na Obr. 4.6 by měla vypadat takhle. Tak jsem se rozhodl kódovat
problém, a všiml si, že výsledky nejsou vždy stabilní (můžete
naznačují, že v cvičení 4.8). Ve skutečnosti, optimalizace je zcela
stabilní, když problém je velikost divné, ale to není problém i pro
rozměry.

Optimální politiky v případě dokonce obvykle předpokládají jakýsi fraktální
vlastnosti, které jsou velmi volatilní během iterace, zatímco
je nějaký fixní základní struktura vyplněných trojúhelníků (z toho vašeho
Na obrázku jsou znázorněny čtyři). Jsem si všiml, že počet naplněných trojúhelníků je
stejně jako moc 2 v problémovou velikost. Jinými slovy, je-li problém
velikost je 2 ^ n * k, kde k je liché, pak řešení blízko
Optimální politika má 2 ^ n vyplněné trojúhelníky v nich plus nějaké těkavé
(Nestabilní) fraktální strukturu. Zejména pokud problém velikost je zvláštní,
pak n = 0, 2 ^ n = 1, a zjistíte, (trvale) jeden plný trojúhelník
to.

Nyní na mé otázky:

1.. Můžete potvrdit mé výše uvedené postřehy?
2.. Víte o jakékoli teoretické zpracování této otázky?
3.. I když moje pozorování se zdají obecně v souladu s výsledkem v
Obr. 4.6 jsem nemohl reprodukovat přesný výsledek pro optimální
politika, pravděpodobně kvůli ztrátě přesnosti výpočtu. Věděli
jste podobné problémy výpočtu řešení, nebo je vaše
vyplývat odvozené z teoretických úvah? Pokud ne, jak jste
vyhnout se přesnost problémy?

Velice vám děkuji za váš čas zodpovězení této otázky,


Daniel Polani

| Institut für Informatik | Staudingerweg 9 |
| Fachbereich Mathematik | 55099 Mainz |
| Johannes Gutenberg-Universität | Německo |
| ————————————————- ————– |
| [email protected], Tel. +6131/39-3608 |
| Http://www.informatik.uni-mainz.de/PERSONEN/Polani.html |

PS: Děkuji moc za vaše hladké, konzistentní a sjednocení
úvod kniha do RL, to bylo velmi užitečné pro mě připravit
můj RL kurz.

Pro: [email protected]
Od: Rich Sutton
Předmět: Re: Dotaz o Gambler je problém ve vaší knize RL

Vážení Daniel Polani,

Díky za milá slova a popisy svých zkušeností výuky posílení učení a pomocí naší knihy. Obávám se, že vám nemůžu dát žádnou definitivní odpověď na problém hazardního hráče. Vzpomínám si na jednu studenta ve třídě jsem se učil z pečlivě prostudovala to především výpočetně, ale nevzpomínám si, že jeho přesné závěry. Co si vzpomínám, myslím, že řešení je uvedeno v knize, je jen jedním z mnoha optimálních politik pro daný úkol. To je možná jeden z hlavních bodů cvičení – řídit domů skutečnost, že existuje mnoho potenciálně optimální politiky vzhledem k tomu, optimální hodnoty jsou jedinečné. Politika jeden najde často má co do činění s triviální věci, jako je numerické řešení nebo pořadí, ve kterém něčí přerušení programu vazby pro maximální referenční hodnotě. To je pravděpodobně důvod, proč jsi nedostal nutně přesně výsledek na obr. 4.6. Věřím, že je to stále optimální politiky, nicméně. Můžete to zkontrolovat pomocí optimální funkci hodnoty jste našli. Uvidíme, jestli moje dlouhodobá politika na místní úrovni max je vaše hodnota funkce v rámci numerické řešení vašeho přístroje. Kód jsem použil je k dispozici na webové stránce pro knihu, pokud chcete zkontrolovat pořadí jsem použil rozbít svazky (nebo chyba v mém kódu!).

Nevím o žádné teoretické analýzy tohoto problému. Vzali jsme tento problém ze standardního textu, pravděpodobně text DP, ale nemohl jsem říct, který teď a já jsem zklamán, že jsme nezaznamenali, které v naší knize. Můžete zkontrolovat cvičení v některé ze starších textů Bertsekas DP. Ale v každém případě, jsme trochu změnili problém, takže jakákoli předběžná analýza nemusí týkat. Pravděpodobně jste nyní pochopili, že problém, stejně jako někdo dělá.

S pozdravem,
Rich Sutton

Od: Daniel Loeb
Pro: Rich Sutton

Mám dotaz ohledně “The Gambler je problém”
který se objeví v příkladu 4.3 ve své knize
“Posílení učení: Úvod”.

Vaše řešení znamená, je tam jen jeden optimální řešení
do hazardního hráče problému.
Například, počínaje 70 dolarů je to jen optimální vsadit 5 dolarů.
Domnívám se, že je optimální vsadit buď $ 5 nebo 20 dolarů nebo 30 dolarů.
Mám něco chybí?

Zde je můj kompletní řešení.

O = vaše řešení
* = Jiná řešení

o
**
**
**
**
**
o o
****
****
O O
o o o o o o o o
o o o o o o o o
0 dolarů 25 dolarů 50 dolarů 75 dolarů 100 dolarů

Zejména jednoduchý politika vždy dělat
největší povolená sázka je optimální.

Zdá se, že kompletní soubor optimální podmínky pro všechny
p méně než 50%.
Počet úrovní třídění se zdá, že závisí na
počet pravomocí 2, které jdou do cíle ($ 100).

Zajímalo by mě, jestli kompletní řešení je známý pro nekonečně
dělitelný peníze. Můžete získat dobrou představu, co by to mohlo vypadat
výběrem jako cíl, který je velký výkon dvou.

Zde je kód jsem použil (v Matlabu) najít své řešení:

Funkce [b, f] = optcasino (n, prob)

postava;
Název (prob);
držet;

v = nuly (1, n-1);

delta = 1;
iter = 0;

while (delta> 1e-50)
iter = iter + 1
[B, v, delta] = kasino (v, prob);
plot (1: (n-1), v);
konec

držet;
% Bar (b);
plot (b (:, 1), B (:, 2), “m * ‘);

=======

Funkce [bnew, vnew, delta] = kasino (vold, prob)

n = 1 + length (vold);

vold = [0, vold, n];
bnew = [];

pro i = 1: (n-1)
Sázky = [1: min (i, n-i)];
vs = prob * vold (1 + i + sázky) + (1-prob) * vold (1 + i-bet);
if (i == 15)
vs – max (VS);
konec
vnew (i) = max (VS);
goodbets = find (vs> = vnew (i) * (1-1e-9));
gbets = ones (délka (goodbets), 2);
gbets (:, 1) = i;
gbets (:, 2) = goodbets “;
bnew = [bnew; gbets];
konec

delta = max (abs ([0, vnew, n] – vold))


S pozdravem, Daniel Loeb, Susquehanna International Group, LLP
http://dept-info.labri.fr/ ~ Loeb
Práce [email protected] 401 City Line, Bala Cynwyd PA 19004 610/617-2671
Domů [email protected]

Datum: pá. 30.listopad 2001 09:00:47 -0500
Pro: Dan Loeb
Od: Andy Barto
Předmět: Re: Vyztužení učení: Příklad 4.3
Cc: Rich Sutton

Dan,
Mnohokrát děkuji za komentář k příkladu 4.3. Ve skutečnosti, se psát jako v případě, že řešení Obr. 4.6 je pouze jeden, v případě, že je celá třída z nich. Odvedl jste dobrou práci charakterizovat celou třídu. Jsme si toho vědomi, a studenti v tomto předmětu jsou podobně popsána všechna řešení. Ale díky moc za vaši zprávu. Budoucí první vydání této knihy bude to lepší.
Sincrely,
A. Barto

PS: Nepřemýšlel jsem o případu nekonečně dělitelné peněz

Od: Francesco.Decomite @ lifl.fr
Předmět: Gambler je problém
Datum: 26.května 2004 06:46:57 MDT
Pro: [email protected]

Vážený pane,

Při studiu si knihu, snažím přepsat a testování algoritmů.
Jsem potýkají s problémem asi týden teď, pracuje na problému hazardního hráče (např 4.3 str. 101):

Bez ohledu na to, jak tvrdě jsem se snažil, nikdy jsem získat dobře tvarovaný dolní graf na obr. 4.6 str. 103, ale pouze přibližné.

I při použití kódu, tvar je přibližné. Dalším bodem je, že, pokud jde o p <0,5, všechny grafy hledají podobně. Já k vám graf získaný z kódu s dvěma hodnotami (p Jen jsem přidal funkci: LP výstupu do konečného politiku) a dělený Epsilon 100.: dobře, přikládám i upravený kód)
Moje otázka tedy je: Myslíte si, získat graf metodami analytickými, nebo jiné způsoby uvažování? Pokud ano, můžete mi dát nějaké rady?

S pozdravem

F. de Comité


Francesco De Comité
tel. (33) 03 28 77 85 72
fax (33) 03 28 77 85 37
www.lifl.fr/ ~ decomite

;, Hazardního hráče problém. Hráč má zájem s mezi 0 a 100. Na každém
;, Hrát se sázkami celé číslo <= y. Vyhrává to hodně s prob p, jinak se
;, Ztratí moc. Kdyby se staví svůj podíl na 100 vyhrává (tedy nikdy
;, Sázky více než (- 100 s)), pokud jeho podíl klesne na 0, že ztratí.

;, Znamená, že sázka je je státní akce jsou velikost nabídky.

;, Zde jsme realizovat hodnotu iterace.

(DefVar v (make-array 101: počáteční-element 0))
(Setf (aref V 100) 1)
(DefVar p 0,12)

(Defun backup-akce (y)
(+ (* P (aref V (+ y)))
(* (- 1 p) (aref V (- y)))))

(Defun vi (a volitelně (epsilon ,0000000001))
“Hodnota iterace na kritériu epsilon”
(Loop sbírat (smyčka pro i od 1 do 99. shromáždit (seznam I (aref vi)))
while ( tato hodnota (+ nejlepší hodnota epsilon))
(Setq nejlepší hodnotu to-value)
(Setq nejlepší akce))
konečně (návrat osvědčené akce)))

(Defun lp ()
(Smyčka pro i od 1 do 99. shromáždit (seznam I (politika i)))
)

Comments are closed.