Factored value iteration converges
In this paper we propose a novel algorithm, factored value iteration (FVI), for the approximate solution of factored Markov decision processes (fMDPs). The traditional approximate value iteration algorithm is modified in two ways. For one, the least-squares projection operator is modified so that it...
Elmentve itt :
| Szerzők: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Cikk |
| Megjelent: |
2008
|
| Sorozat: | Acta cybernetica
18 No. 4 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12838 |
| LEADER | 01778nab a2200241 i 4500 | ||
|---|---|---|---|
| 001 | acta12838 | ||
| 005 | 20220616154723.0 | ||
| 008 | 161015s2008 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Szita István | |
| 245 | 1 | 0 | |a Factored value iteration converges |h [elektronikus dokumentum] / |c Szita István |
| 260 | |c 2008 | ||
| 300 | |a 615-635 | ||
| 490 | 0 | |a Acta cybernetica |v 18 No. 4 | |
| 520 | 3 | |a In this paper we propose a novel algorithm, factored value iteration (FVI), for the approximate solution of factored Markov decision processes (fMDPs). The traditional approximate value iteration algorithm is modified in two ways. For one, the least-squares projection operator is modified so that it does not increase max-norm, and thus preserves convergence. The other modification is that we uniformly sample polynomially many samples from the (exponentially large) state space. This way, the complexity of our algorithm becomes polynomial in the size of the fMDP description length. We prove that the algorithm is convergent. We also derive an upper bound on the difference between our approximate solution and the optimal one, and also on the error introduced by sampling. We analyse various projection operators with respect to their computation complexity and their convergence when combined with approximate value iteration. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 700 | 0 | 1 | |a Lőrincz András |e aut |
| 710 | |a Symposium of Young Scientists on Intelligent Systems (2.) (2007) (Budapest) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12838/1/Szita_2008_ActaCybernetica.pdf |z Dokumentum-elérés |