Dice enterprises as imperfect-recall games

I have put a probability theory preprint on arXiv: Dice enterprises and polynomial approximation: uniform query tails . Abstract: A binary-output dice enterprise uses independent rolls of a die with unknown face probabilities to simulate a coin with bias . We determine which power-law tails, uniform over the closed probability simplex, are attainable for the number of rolls. For continuous with values in and , some enterprise for satisfies if and only if can be approximated uniformly by polynomials of degree with error . When this holds, the tail is attained by an oblivious enterprise, which chooses its number of rolls before rolling. The characterization extends to any fixed finite output alphabet when its probabilities are uniformly positive, and to several input dice, with total degree on a product of simplices; in the latter case it suffices to roll the dice in a fixed cyclic order. For , these enterprises have a uniformly bounded expected number of rolls. In this post, I give a decision-theoretic motivation for the problem, which will hopefully be more accessible than the paper itself. Imperfect-recall games with countably many states Much work on imperfect-recall games assumes a finite game tree. In that case, the player's expected utility is a polynomial in their policy. Here is an MDP-like formulation that permits a countably infinite set of states. Let be a finite set of observations. For each observation , let be the finite set of actions allowed given observation…