Relational Reinforcement Learning - Decreasing Game State Spaces Through Generalization
Author
Jensen, Klaus
Term
4. term
Education
Publication year
2004
Abstract
Mange machine learning-opgaver er svære, fordi systemet skal håndtere et enormt 'tilstandsrum'—mængden af alle mulige situationer. At finde den bedste handling i et sådant rum kræver meget beregning. Denne rapport er en del af et projekt, der undersøger måder at formindske tilstandsrum i små computerspil. Vi fokuserer på forstærkningslæring (Reinforcement Learning, RL), hvor en agent gennem forsøg og fejl lærer, hvilke handlinger der giver belønning. En udbredt metode, tabelbaseret Q-learning, gemmer en værdi for hver kombination af tilstand og handling og får derfor problemer, når antallet af tilstande bliver for stort. Vi undersøger relationel forstærkningslæring (Relational Reinforcement Learning, RRL), som udvider klassisk RL med relationelle repræsentationer udtrykt i første-ordens logik—et formelt sprog til at beskrive objekter og relationer mellem dem. Ved at beskrive situationer som relationer (fx hvilken klods der ligger på hvilken) sigter RRL mod en mere kompakt repræsentation end flade, tabelbaserede tilgange. Som legetøjseksempel bruger vi Blocks World til at vise, hvor RRL er stærk, og hvor metoden har begrænsninger. Til sidst præsenterer vi Tetris Limited, en reduceret udgave af Tetris, og implementerer det ved hjælp af RL.
Many machine learning tasks are difficult because the system must handle an enormous 'state space'—the set of all possible situations it can encounter. Finding the best action in such a space requires heavy computation. This report is part of a project that explores ways to shrink the effective state space in small computer games. We focus on Reinforcement Learning (RL), where an agent learns through trial and error which actions lead to rewards. A common method, table-based Q-learning, stores a value for every state–action pair and therefore struggles when there are too many states. We examine Relational Reinforcement Learning (RRL), which extends conventional RL with relational representations expressed in First-Order Logic—a formal language for describing objects and the relations between them. By describing situations in terms of relations (for example, which block is on top of which), RRL aims to represent environments more compactly than flat, table-based approaches. Using the classic Blocks World as a toy domain, we illustrate where RRL is strong and where it is limited. Finally, we present Tetris Limited, a simplified version of Tetris, and implement it using RL.
[This abstract was generated with the help of AI]
Documents