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

Speaker: Richard Mayr

**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