The paper presents an approach for developing multi-agent reinforcement learning systems that are made up of a coalition of modular agents. We focus on learning to segment sequences (sequential decision tasks) to create modular structures, through a bidding process that is based on reinforcements received during task execution. The approach segments sequences (and divides them up among agents) to facilitate the learning of the overall task. Notably, our approach does not rely on a priori knowledge or a priori structures. Initial (...) experiments demonstrated the basic promise of the approach. This work shows how bidding and reinforcement learning can be usefully combined, thus pointing to a new research direction. (shrink)

Although hierarchical approaches are evidently important to reinforcement learning, most existing hierarchical RL models either do not involve automatically developing hierarchies (i.e., using pre-determined hierarchies; e.g., Dayan and Hinton 1993, Sutton 1995, Pre-cup et al 1998, Parr and Russell 1997, Dietterich 1997), or involve only domain-speci c processes. Models in the latter category rely on domain-speci c knowledge or procedures and are thus not generic or autonomous; for example, Lin (1993), Moore and Atkeson (1994), and Singh (1994). The problems of (...) such hierarchies include in exibility (because the characteristics of the domain can change over time) and lack of generality (because domain-speci c hierarchies most likely vary from domain to domain). This is true even when limited learning is used to ne tune mostly pre-determined hierarchies (e.g., Parr and Russell 1997, Dietterich 1997). (shrink)

This paper is concerned with autonomous learning of plans in probabilistic domains without a priori domain-specific knowledge. In contrast to existing reinforcement learning algorithms that generate only reactive plans and existing probabilistic planning algorithms that require a substantial amount of a priori knowledge in order to plan, a two-stage bottom-up process is devised, in which first reinforcement learning/dynamic programming is applied, without the use of a priori domain-specific knowledge, to acquire a reactive plan and then explicit plans are extracted from (...) the reactive plan. Several options for plan extraction are examined, each of which is based on a beam search that performs temporal projection in a restricted fashion, guided by the value functions resulting from reinforcement learning/dynamic programming. Some completeness and soundness results are given. Examples in several domains are discussed that together demonstrate the working of the proposed model. (shrink)