Personal tools
You are here: Home Events Lab Lunch Talk: The 1-bit Saga: The Solution of a 40 Year old Problem in Gambling

Lab Lunch Talk: The 1-bit Saga: The Solution of a 40 Year old Problem in Gambling

Speaker: Richard Mayr

What
When Dec 17, 2019
from 01:00 PM to 02:00 PM
Where MF2
Add event to calendar vCal
iCal

Abstract:

Given a countable Markov decision process (MDP) and a set of goal states, how can one visit the goal states infinitely often, with high probability? Optimal strategies need not exist.

How much memory do epsilon-optimal strategies need? In 1979 T.P. Hill (a student of Lester Dubbins, of Dubbins & Savage "How to Gamble If You Must") proved that Markov strategies (i.e., just using a clock) suffice if the number of controlled states is finite. The general case remained open until 2019, and has a surprising solution. The strategies need exactly a clock and 1 extra bit of memory.

Reference:

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke.

B├╝chi Objectives in Countable MDPs. ICALP 2019, LIPIcs, Vol. 132.

Athens, Greece. 2019

http://arxiv.org/abs/1904.11573


Document Actions