%0 Report %1 kalmarsze1999 %A Kalmár, Zs. %A Szepesvári, Cs. %C Budapest 1121, Konkoly Th. M. u. 29-33, HUNGARY %D 1999 %K learning learning, lifelong macro multitask reinforcement %N TR-99-01 %T An Evaluation Criterion for Macro-Learning and Some Results %X It is known that a well-chosen set of macros makes it possible to considerably speed-up the solution of planning problems. Recently, macros have been considered in the planning framework, built on Markovian decision problem. However, so far no systematic approach was put forth to investigate the utility of macros within this framework. In this article we begin to systematically study this problem by introducing the concept of multi-task MDPs defined with a distribution over the tasks. We propose an evaluation criterion for macro-sets that is based on the expected planning speed-up due to the usage of a macro-set, where the expectation is taken over the set of tasks. The consistency of the empirical speed-up maximization algorithm is shown in the finite case. For acyclic systems, the expected planning speed-up is shown to be proportional to the amount of ``time-compression'' due to the macros. Based on these observations a heuristic algorithm for learning of macros is proposed. The algorithm is shown to return macros identical with those that one would like to design by hand in the case of a particular navigation like multi-task MDP. Some related questions, in particular the problem of breaking up MDPs into multiple tasks, factorizing MDPs and learning generalizations over actions to enhance the amount of transfer are also considered in brief at the end of the paper.

@techreport{kalmarsze1999, abstract = {It is known that a well-chosen set of macros makes it possible to considerably speed-up the solution of planning problems. Recently, macros have been considered in the planning framework, built on Markovian decision problem. However, so far no systematic approach was put forth to investigate the utility of macros within this framework. In this article we begin to systematically study this problem by introducing the concept of multi-task MDPs defined with a distribution over the tasks. We propose an evaluation criterion for macro-sets that is based on the expected planning speed-up due to the usage of a macro-set, where the expectation is taken over the set of tasks. The consistency of the empirical speed-up maximization algorithm is shown in the finite case. For acyclic systems, the expected planning speed-up is shown to be proportional to the amount of ``time-compression'' due to the macros. Based on these observations a heuristic algorithm for learning of macros is proposed. The algorithm is shown to return macros identical with those that one would like to design by hand in the case of a particular navigation like multi-task MDP. Some related questions, in particular the problem of breaking up MDPs into multiple tasks, factorizing MDPs and learning generalizations over actions to enhance the amount of transfer are also considered in brief at the end of the paper.}, added-at = {2020-03-17T03:03:01.000+0100}, address = {Budapest 1121, Konkoly Th. M. u. 29-33, HUNGARY}, author = {Kalm{\'a}r, {Zs}. and Szepesv{\'a}ri, {Cs}.}, biburl = {https://www.bibsonomy.org/bibtex/213e8992fa9b1f787cd2ec957d97cd0d9/csaba}, date-modified = {2010-09-02 13:09:15 -0600}, institution = {Mindmaker Ltd.}, interhash = {0a9d4b8ead4a3f927e608cd001f435ec}, intrahash = {13e8992fa9b1f787cd2ec957d97cd0d9}, keywords = {learning learning, lifelong macro multitask reinforcement}, number = {TR-99-01}, owner = {Beata}, pdf = {papers/macro-tr99-01.ps.pdf}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {An Evaluation Criterion for Macro-Learning and Some Results}, year = 1999 }