- author = "Marco Wiering and Juergen Schmidhuber",
- title = "Solving {POMDPs} with {Levin} search and {EIRA}",
- booktitle = "Machine Learning: Procceedings of 13th International Conference",
- year = "1996",
- editor = "Lorenza Saitta",
- pages = "534--542",
- address = "Bari, Italy",
- publisher = "Morgan Kaufmann Publishers",
- keywords = "genetic algorithms, genetic programming",
-
URL = "
ftp://ftp.idsia.ch/pub/marco/ml_levin_eira.ps.gz",
-
URL = "
ftp://ftp.idsia.ch/pub/juergen/icmllevineira.pdf",
-
URL = "
http://www.idsia.ch/~juergen/icmllevineira/",
-
biburl = "https://dblp.org/rec/conf/icml/WieringS96.bib",
- size = "9 pages",
- abstract = "Partially observable Markov decision problems (POMDPs) recently received a lot of attention in the reinforcement learning community. No attention, however, has been paid to Levin universal search through program space (LS), which is theoretically optimal for a wide variety of search problems including many POMDPs. Experiments in this paper first show that LS can solve partially observable mazes (POMs) involving many more states and obstacles than those solved by various previous authors (here, LS also can easily outperform Q-learning). We then note, however, that LS is not necessarily optimal for incremental learning problems where experience with previous problems may help to reduce future search costs. For this reason, we introduce an adaptive extension of LS (ALS) which uses experience to increase probabilities of instructions occurring in successful programs found by LS. To deal with cases where ALS does not lead to long term performance improvement, we use the recent technique of environment-independent reinforcement acceleration (EIRA) as a safety belt (EIRA currently is the only known method that guarantees a lifelong history of reward accelerations). Experiments with additional POMs demonstrate: (a) ALS can dramatically reduce the search time consumed by successive calls of LS. (b) Additional significant speed-ups can be obtained by combining ALS and EIRA.",
-
notes = "Details to GP list on Wed, 24 Jul 1996 13:57:22
+0200
To appear in Proc. ICML`96, 86 K, 252 K uncompressed. Another spin-off paper of the TR (schmidhuber:1996:spm?) above. It uses ``Levin's universal search through program space (LS)''. LS is theoretically `optimal' for a wide variety of search problems including many partially observable Markov decision problems (POMDPs). Experiments show that LS can solve partially observable mazes (`POMS') involving many more states and obstacles than those solved by various previous authors. An adaptive extension of LS (ALS) is introduced. ALS uses experience to increase probabilities of instructions occurring in successful programs found by LS. To deal with cases where ALS does not lead to long term performance improvement, we use the above-mentioned, novel paradigm (EIRA) to guarantee lifelong histories of reward accelerations. We show: (a) ALS can dramatically reduce the search time consumed by successive calls of LS. (b) Additional significant speedups can be obtained by combining ALS with EIRA.
1996 FRIDAY July 5 11:30-13:00 Parallel Session A https://icml.cc/Conferences/1996/",
