CS 670 Final Exam Review Sheet

13 December 2006

The final is comprehensive

Refer to the previous review sheets.

Multi-agent Learning

• Satisficing
• Aspiration update
• Algorithm
• Relaxation search
  
• The multi-agent social dilemma (MASD)
  
• Properties of the Satisficing algorithm
• Security against  exploiting opponents (and switching to a pure strategy maximin if needed)
• Efficiency in self play on the MASD
  

Multi-agent Learning

• Minimax Q learning algorithm
• Philosophy: Minimax values
• Hu and Wellman's algorithm
• Philosophy: Nash equilibrium
• Q-values for every agent
  
• Computing the expected discounted value for the next state
• Complexity: time and space
  
• PHC
• Philosophy
• WoLF
• Philosophy
• WoLF principle
• Storage and knowledge requirements
• Lessons from the lab
  

Multi-agent Search

• Asynchronous dynamic programming
• algorithm
• philosophy
• LRTA*
• algorithm
• initialization
• intuition of convergence proof
• Moving Target Search
• assumptions
• algorithm
• heuristic error and disparity
• proof of convergence and completeness
• Bi-directional search
• using LRTA*
• using MTS