We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O (log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman.
展开▼
机译：我们研究具有吸收状态的重复游戏，这是一种两人，零和并发均值支付游戏，其典型示例是吉列特（Bigille of Gillete）（1957）。这些博弈可能不允许最优策略，但它们始终具有ε最优策略。在本文中，我们在这些仅使用O（对数T）空间的游戏中为玩家1设计了ε最优策略。此外，针对任意小的无界非递减函数s，我们构造了使用空间s（T）的播放器1的策略，并在极限上级意义上保证了播放器1的ε最优值。先前已知的策略使用空间Ω（log T），并且即使在最佳极限意义上，如果它是ε最优的，也没有策略可以使用恒定空间。我们还给出了一个互补的下限。此外，我们还表明，即使使用有限记忆扩展的马尔可夫策略也无法确保大匹配中的值大于0，从而回答了内曼提出的问题。
展开▼
