Lab Lunch: 20 November 2018 - Richard Mayr

Title: Memory in Strategies: What is it used for?

Abstract:

We consider various types of games on finite or infinite graphs, e.g. non-stochastic 2-player games, games against nature (aka Markov Decision Processes) and 2-player stochastic games.

Depending on the objective of the game, optimal strategies (where they exist) or epsilon-optimal strategies may or may not need to use a certain amount of memory. Objectives are often classified by whether no memory, finite memory or infinite memory is required (in addition to randomization).

We give an overview over the typical reasons why memory is required and how the strategies actually use the memory, i.e. what information needs to be stored.