Nie rozumiem algorytmu, ale próbuję sobie jakoś to poukładać.
Z tego co napisałeś:
- Są stany świata (S1, ..., Sn)
- Są możliwe akcje do wykonania przez agenta (A1, ..., Am)
- Akcje skutkują przejściem z obecnego stanu do innego stanu.
W ogólności akcja A_k skutkuje przejściem ze stanu S_i do S_j z prawdopodobieństwem p_ijk:
- 0<= p_ijk <=1
- Dla ustalonego stanu S_i i akcji A_k , suma po j=1..n p_ijk = 1 (czyli zadajemy prawdopodobieństwa do przejścia z ustalonego stanu, do innego stanu, niektóre być może 0 <- przejście nie jest dozwolne)
-
p_ijk zależą od stanu ukrytego, ale nie wiesz jaki jest "prawdziwy" rozkład
-
Masz funkcję, którą optymalizujesz.
Czy działa to mniej więcej tak?
a) Ten rozkład p_ijk to Twój "belief" ?
b) Czy Twój algorytm aktualizuje prawdopodobieństwa p_ijk ? (odnoszę wrażenie, że tak <- na podstawie przykładu z wyborem bramki )
c) Czy Twój algorytm buduje drzewo: wykonam akcję A_1 i wyliczę wartość oczekiwaną, wykonam akcję A_2 i wyliczę wartość oczekiwaną, ..., wykonam akcję A_m i wyliczę wartość oczekiwaną -> wybieram maxa
d) Agent wykonuje akcję dającą maxa i obserwuje co się dzieje ? W przypadku gdy źle wybrał, to aktualizuję rozkład prawdopodobieństwa ? (W jaki sposób ta korekta jest liczona?)
To rzecz jasna moje wyobrażenie jak to działa (mój "belief" ;) ) i może działa zupełnie inaczej.
a). Nie, belief to coś innego. To o czym piszesz p_ijk to model. Belief to rozkład nad możliwymi stanami zawężonymi do stanu obserwowalnego. Weźmy taki przykład:
variables
{
input variable alpha:{false,true};
hidden variable beta:{false,true};
output variable gamma:{false,true};
}
Stanem obserwowalnym jest np. alpha=>false. Odpowiadają mu w naturalny sposób dwa stany: {alpha=>false,beta=>false} i {alpha=>false,beta=>true}. Belief jest rozkładem nad tymi dwoma stanami i nie ma nic wspólnego z modelem. Inny stan obserwowalny to alpha=>true. Odpowiadają mu dwa stany (chciałoby się rzec "ukryte") a mianowicie {alpha=>true,beta=>false} i {alpha=>true,beta=>true}. Znowuż belief dla tego stanu obserwowalnego byłby jakimś rozkładem nad tymi dwoma stanami.
Natomiast model wygląda być może tak (w Perkunie):
model
{
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>false ,beta=>false },0.10000);
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>false ,beta=>true },0.20000);
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>true ,beta=>false },0.30000);
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>true ,beta=>true },0.40000);
....
}
b). Nie, mój algorytm nie aktualizuje modelu. Model jest stały, z góry zadany. Aktualizuje belief.
c). Prawie tak. Funkcja get_optimal_action rozważa wszystkie akcje, dla każdej akcji A1 rozważane są wszystkie stany obserwowalne VS1, konstruowany jest nowy belief B2 i dla niego z kolei rozważamy wszystkie akcje, dla każdej akcji A2 rozważane są wszystkie stany obserwowalne VS2, konstruowany jest nowy belief B3 itd. Z funkcji get_optimal_action zwracany jest argmax funkcji get_payoff_expected_value_for_consequences.
d). Rozumiem, że odnosisz się do paradoksu MontyHall. Nie. Po prostu za każdym razem stara się zmaksymalizować wartość oczekiwaną funkcji payoff. Aktualizuje belief ZAWSZE, nie tylko gdy źle wybrał. Po prostu musi to zrobić, żeby dostosować belief do nowej sytuacji (nowych wartości na wejściu). Robi to uwzględniając poprzedni belief, wykonaną akcję, otrzymaną odpowiedź (stan widoczny) i model.
To jak belief jest aktualizowany to już moja słodka tajemnica. Żartuję, tak naprawdę to treść funkcji optimizer::populate_belief_for_consequence. To jest funkcja używana w dwóch miejscach - w normalnej pętli (loop), żeby zareagować na kolejny sygnał na wejściu (zinterpretować rezultat otrzymany z ostatnio wykonanej akcji) oraz w planowaniu, przy przejściu do kolejnego węzła drzewa gry. Możesz sprawdzić, że mówię prawdę odpalając w katalogu Svaroga polecenie:
find src -type f -exec grep -H "populate_belief_for_consequence" {} \;
Wyjdzie, że oprócz definicji mamy tylko jedno użycie w src/optimizer.cc (to jest to planowanie) i jedno w command_loop.cc (to jest zwykła interpretacja ostatniego rezultatu).
Żeby sobie wyobrazić czym jest mój model proponuję odpalić w Perkunie specyfikację:
values
{
value false, true;
}
variables
{
input variable alpha:{false,true};
hidden variable beta:{false,true};
output variable gamma:{false,true};
}
payoff
{
}
model
{
}
cout << model << eol;
To wygeneruje ciąg zaczynający się od:
# model
# {gamma=>false}
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>false ,beta=>false },0.00000);
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>false ,beta=>true },0.00000);
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>true ,beta=>false },0.00000);
set({alpha=>false ,beta=>false },{gamma=>false },{alpha=>true ,beta=>true },0.00000);
# {gamma=>true}
set({alpha=>false ,beta=>false },{gamma=>true },{alpha=>false ,beta=>false },0.00000);
set({alpha=>false ,beta=>false },{gamma=>true },{alpha=>false ,beta=>true },0.00000);
set({alpha=>false ,beta=>false },{gamma=>true },{alpha=>true ,beta=>false },0.00000);
set({alpha=>false ,beta=>false },{gamma=>true },{alpha=>true ,beta=>true },0.00000);
# {gamma=>false}
set({alpha=>false ,beta=>true },{gamma=>false },{alpha=>false ,beta=>false },0.00000);
set({alpha=>false ,beta=>true },{gamma=>false },{alpha=>false ,beta=>true },0.00000);
set({alpha=>false ,beta=>true },{gamma=>false },{alpha=>true ,beta=>false },0.00000);
set({alpha=>false ,beta=>true },{gamma=>false },{alpha=>true ,beta=>true },0.00000);
...
Z prawdopodobieństwami ustawionymi na zero. To nie jest oczywiście poprawny model, w każdej takiej czwórce prawdopodobieństwa muszą się sumować do jedności, ale pomaga zrozumieć jak duże są modele.