next up previous
Next: Levin Search (LS) Up: Shifting Inductive Bias with Previous: Basic Set-Up and SSA

Implementation 1: Plugging LS into SSA

Overview. In this section we introduce an adaptive extension of Levin search (LS) [#!Levin:73!#,#!Levin:84!#] as only learning action to be plugged into the basic cycle. We apply it to partially observable environments (POEs) which recently received a lot of attention in the RL community, e.g., [#!Whitehead:90!#,#!Schmidhuber:91nips!#,#!Lin:93!#,#!Ring:94!#,#!Littman:94!#,#!Cliff:94!#,#!Chrisman:92!#,#!Jaakkola:95!#,#!Kaelbling:95!#,#!McCallum:95!#]. We first show that LS by itself can solve partially observable mazes (POMs) involving many more states and obstacles than those solved by various previous authors (we will also see that LS can easily outperform Q-learning). We then extend LS to combine it with SSA. In an experimental case study we show dramatic search time reduction for sequences of more and more complex POEs (``inductive transfer'').



Subsections

Juergen Schmidhuber 2003-02-25


Back to Optimal Universal Search page
Back to Reinforcement Learning page
Back to Program Evolution page