Mark Humphrys - Research - PhD

Help if the mathematics does not display Search:   Help on Search

Action Selection methods using
Reinforcement Learning

Mark Humphrys

Trinity Hall




A dissertation submitted for the degree of Doctor of Philosophy
in the University of Cambridge

This is the expanded version of my PhD, produced as Technical Report No. 426 in June 1997.
This document can be printed as a single PostScript file here.

Abstract

The Action Selection problem is the problem of run-time choice between conflicting and heterogenous goals, a central problem in the simulation of whole creatures (as opposed to the solution of isolated uninterrupted tasks). This thesis argues that Reinforcement Learning has been overlooked in the solution of the Action Selection problem. Considering a decentralised model of mind, with internal tension and competition between selfish behaviors, this thesis introduces an algorithm called "W-learning", whereby different parts of the mind modify their behavior based on whether or not they are succeeding in getting the body to execute their actions. This thesis sets W-learning in context among the different ways of exploiting Reinforcement Learning numbers for the purposes of Action Selection. It is a `Minimize the Worst Unhappiness' strategy. The different methods are tested and their strengths and weaknesses analysed in an artificial world.

Contents

• 1 The Action Selection problem [Start Here]
  • 1.1 Terminology
  • 1.2 Notation
  • 1.3 A brief guide to this dissertation
• 2 Reinforcement Learning
  • 2.1 Q-learning
    • 2.1.1 Special case - Deterministic worlds
    • 2.1.2 Special case - Different action sets
    • 2.1.3 Notes on expected reward
    • 2.1.4 The task
    • 2.1.5 The strategy
    • 2.1.6 How Q-learning works
    • 2.1.7 Notes on building a world model
  • 2.2 Discrete Q-learning
    • 2.2.1 Convergence
    • 2.2.2 Discussion
    • 2.2.3 The control policy
    • 2.2.4 Special case - Absorbing states
• 3 Multi-Module Reinforcement Learning
  • 3.1 Hierarchical Q-learning
• 4 The House Robot problem
  • 4.1 Simulations and Artificial Worlds
    • 4.1.1 Separation of world from user interface
  • 4.2 Notes on MDP
  • 4.3 Test of Q-learning
    • 4.3.1 Designing a Global reward function
    • 4.3.2 Neural network implementation
    • 4.3.3 Hand-coded programs
  • 4.4 Test of Hierarchical Q-learning
    • 4.4.1 Q-learning with subspaces
    • 4.4.2 Learning Q together
    • 4.4.3 Designing Local reward functions
• 5 An abstract decentralised model of mind
  • 5.1 The weight W
  • 5.2 W = Drive Strength
  • 5.3 Static W=Q
  • 5.4 Static W = importance
    • 5.4.1 Static W=z
  • 5.5 Dynamic (learnt) W-values
    • 5.5.1 Dynamic W = D - F
  • 5.6 A walk through the matrix
    • 5.6.1 Multiple possible winners
• 6 W-learning (Minimize the Worst Unhappiness)
  • 6.1 Comparison of Q-learning and W-learning
  • 6.2 Progress of competition
    • 6.2.1 Convergence
  • 6.3 Scoring
  • 6.4 Strict highest W
  • 6.5 Stochastic highest W
  • 6.6 W-learning with subspaces
    • 6.6.1 Agents with heterogenous sensory worlds
• 7 W-learning with subspaces (preliminary test in Ant World)
  • 7.1 Analysis of best food-finding solution
    • 7.1.1 Negative W-values
  • 7.2 Analysis of best predator-avoiding solution
  • 7.3 MPEG Movie demo of basic W-learning
    • 7.3.1 Rewarding on transitions or continuously
• 8 W-learning with subspaces (test in House Robot)
  • 8.1 Searching for well-balanced collections
    • 8.1.1 Making agents weaker or stronger
    • 8.1.2 Making agents weaker or stronger without re-learning Q
    • 8.1.3 No Global reward function
  • 8.2 Analysis of best solution
• 9 W=Q (Maximize the Best Happiness)
  • 9.1 Discussion
  • 9.2 Happiness and Unhappiness
• 10 W-learning with full space
  • 10.1 Strict highest W
  • 10.2 Stochastic highest W
• 11 Negotiated W-learning
  • 11.1 Reactiveness
• 12 Collective methods
  • 12.1 Maximize Collective Happiness
  • 12.2 Collective W-learning (Minimize Collective Unhappiness)
    • 12.2.1 Strict lowest W
    • 12.2.2 Stochastic lowest W
    • 12.2.3 Collective W-learning with subspaces
    • 12.2.4 Negotiated Collective W-learning
  • 12.3 Expected performance of Collective methods
  • 12.4 Collective Equality
• 13 Minimize the Worst Unhappiness (revisited)
  • 13.1 Pure Minimize the Worst Unhappiness
  • 13.2 Global v. Decentralised Calculations
• 14 Summary
  • 14.1 The four approaches
  • 14.2 Winner-take-all v. Compromise actions
  • 14.3 Single-Mindedness

  
  

• 15 Related work
  • 15.1 Ethology
    • 15.1.1 Time-based action selection
    • 15.1.2 Low-priority activities
    • 15.1.3 Dithering and Persistence
    • 15.1.4 McFarland
  • 15.2 Hierarchical models
    • 15.2.1 Brooks' Subsumption Architecture
    • 15.2.2 Hierarchies in Ethology
    • 15.2.3 Nested Q-learning
    • 15.2.4 Feudal Q-learning
  • 15.3 Serial models
    • 15.3.1 Singh's Compositional Q-learning
    • 15.3.2 Wixson
    • 15.3.3 Maes' Spreading Activation Networks
  • 15.4 Parallel models
    • 15.4.1 Lin's Hierarchical Q-learning
    • 15.4.2 Pandemonium
    • 15.4.3 Competitive Learning
    • 15.4.4 Jackson
    • 15.4.5 The DAMN Architecture
    • 15.4.6 The BSA Architecture
    • 15.4.7 Drives
    • 15.4.8 Tyrrell
    • 15.4.9 Modular Q-learning (University of Rochester)
    • 15.4.10 W-learning
  • 15.5 Classifier Systems
    • 15.5.1 Grefenstette
    • 15.5.2 Product Maximize Collective Happiness
    • 15.5.3 The Economy of Mind
  • 15.6 Operating Systems Theory
  • 15.7 Ethernet protocols
  • 15.8 Game Theory
  • 15.9 Economic Theory
  • 15.10 Political Theory
• 16 Conclusion
  • 16.1 Empirical results
    • 16.1.1 Hand-coded programs
  • 16.2 Related work
  • 16.3 Searching for the best solution relative to some global score
    • 16.3.1 The Adaptive Landscape
  • 16.4 What global policy have we learnt?
    • 16.4.1 How do we maximise the ongoing sum of rewards?
    • 16.4.2 What the Global reward function cannot express

  
  

• 17 Further work
  • 17.1 Further empirical work
  • 17.2 Scaling up Reinforcement Learning
    • 17.2.1 What problems can this be applied to?
    • 17.2.2 Competition in Single Goal problems
  • 17.3 Different source of numbers
    • 17.3.1 Symbolic W-learning
  • 17.4 Parallel W-learning
  • 17.5 The Bottom-up Animat approach
  • 17.6 Dynamically changing collections of agents
    • 17.6.1 The Ecosystem of Mind
    • 17.6.2 Invasion of strong new agents
• 18 The general form of a Society of Mind based on Reinforcement Learning
  • 18.1 Nested W-learning
    • 18.1.1 The generic form of Nested W-learning
  • 18.2 Feudal W-learning
  • 18.3 The wasteful, overlapping mind

  
  

• Acknowledgements
• A Incremental sampling of random variables
  • A.1 Single variable (average)
  • A.2 Single variable (time-weighted)
  • A.3 Multiple variables
• B Bounds
  • B.1 Bounds with a learning rate
  • B.2 Bounds of Q-values
  • B.3 Bounds of W-values
• C 2-reward reward functions
  • C.1 Policy in Q-learning
  • C.2 Strength in W-learning
  • C.3 Normalisation
  • C.4 Exaggeration
• D 3-reward (or more) reward functions
  • D.1 Policy in Q-learning
  • D.2 Strength in W-learning
  • D.3 Normalisation
  • D.4 Exaggeration
• E Weighted sum and weighted mean
• F Full list of action selection methods
  • F.1 Search for compromise action
  • F.2 Use only suggested actions
• G Experimental Details
• References

Chapter 1

Return to publications or home page.