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 . The countable set of states is , a disjoint union of non-terminal and terminal states. Terminal states have utilities ; as long as utilities are bounded, the restriction to is without loss of generality. Non-terminal states have observations . Given a non-terminal state and action , the transition probabilities are ; transitions may be to any state . The initial state is drawn from a probability distribution over . The player's policy (action probabilities given observation) is denoted , where . Starting in the initial state sampled from , the player repeatedly observes of the present state, selects an action, and transitions to a new state, until reaching a terminal state.

As usual in imperfect-recall games, the player has no intrinsic memory, although they can still "observe" information relevant to their history. Call an imperfect-recall game all-state terminating when, for any non-terminal starting state and any policy, play terminates with probability 1. For all-state terminating imperfect-recall games, the Bellman equations have unique bounded solutions:

Conceptually, is the expected utility of following from state , is the expected utility of taking action in state (the "Q-value"), and is the ex ante (i.e. initial) expected utility of following policy .

We can convert any imperfect-recall game to an "equivalent" one with only terminal utilities in , as follows. Use only two terminal states, one worth 0 and one worth 1. Replace transitions to the original game's terminal states (and -initializations to terminal states) with transitions/initializations to a mixture of the two new terminal states. For example, instead of transitioning to some terminal state with , transition to the 0-value state with probability 0.4 and to the 1-value state with probability 0.6. This transformation preserves the probabilities of all sequences of visited non-terminal states, and all expected utilities.

We can also ensure that the original game's terminal utilities all lie in for some while keeping the incentives the same (by affinely rescaling utilities), so that each ; the -utility transformation preserves this condition on . This matters because the main theorem below is about functions with values in .

Dice enterprises

Now for a superficially different problem. Suppose we have a finite list of dice numbered . Die has faces. The weightings of the dice are given by probability distributions , where , the set of distributions over outcomes. There is some known function mapping joint die weightings to probabilities. We ask: for which does there exist a procedure which repeatedly picks a die and rolls it, as many times as it likes, terminating almost surely with an outcome in , such that for any die weightings, the probability that the procedure returns 1 equals of those weightings?

Such a procedure is called a dice enterprise for . The case of multiple input dice mostly reduces to the single-die case; the basic idea is to represent "one outcome assigned to each input die" as an outcome of a single die with faces. The most commonly studied kind of dice enterprise is a Bernoulli factory, where there is a single input "die" with two outcomes (usually conceptualized as a coin). Throughout, we allow free use of flips of a known-fair coin, although this convention is not universal in the literature.

We can ask that dice enterprises satisfy some bound on query complexity, i.e. the number of input rolls. If there is a hard cap on the number of rolls, then the enterprise can only implement polynomial functions. With no hard cap, we can still ask about tail bounds.

The correspondence

We draw an analogy between imperfect-recall games (with terminal utilities) and dice enterprises as follows:

• Observation ⇔ input die
• Action ⇔ face of input die
• Policy ⇔ weightings of input dice
• Terminal state ⇔ state where the dice enterprise returns a outcome
• Non-terminal state ⇔ state where the dice enterprise rolls an input die
• Initial state distribution ⇔ running the dice enterprise from the beginning until it either returns an outcome or decides to roll an input die
• Expected utility of policy ⇔ probability the dice enterprise returns 1 given die weightings
• Imperfect-recall game with ⇔ dice enterprise implementing
• Number of non-terminal states visited ⇔ number of input die rolls

This analogy basically works once some subtleties around termination (e.g. all-state termination) are handled. So the question of whether an imperfect-recall game with exists (with some bound on the distribution of the number of non-terminal states visited) becomes the question of whether a dice enterprise for exists (with some bound on the number of input die rolls).

For imperfect-recall games, we care about whether there is a finite bound, uniform over all policies, on the expected number of non-terminal states visited starting from the beginning. There is a good practical reason for this: such a bound is required to bound the expected computational cost of simulating the game. Additionally, this condition ensures that "SIA" or "generalized thirding" (GT) probabilities are well-defined. If are random variables for the non-terminal states visited, then GT probabilities for non-terminal states given a policy and observation are:

where is the Iverson bracket. That is, among non-terminal states compatible with the observation, GT probabilities are proportional to the expected number of visits to that state. To ensure these expectations are finite, we would like for all policies ; this condition is weaker than the condition of a uniform bound over all . GT probabilities have applications in, for example, characterizing KKT points as CDT+GT equilibria.

The result

Translated into the language of dice enterprises, we would like dice enterprises whose expected number of input rolls is bounded uniformly across all possible die weightings. The paper does not exactly characterize the functions that have such dice enterprises. However, it gets close: letting be the number of input die rolls, it characterizes the functions (from die weightings to ) which have dice enterprises satisfying the uniform tail bound

This is almost as good, because if a uniform bound on expected rolls exists, then the above condition holds with (by Markov's inequality); and conversely, if the above condition holds with any , then expected rolls are uniformly bounded, as .

Below, is the product of simplices (the set of possible multi-die weightings), and measures how well can be approximated by polynomials of total degree at most . Quoting the paper:

Let and let be continuous. The following are equivalent: (i) Some multi-die enterprise for satisfies (ii) With degree meaning total degree in all coordinates of the product, When these hold, the tail bound in (i) is attained by an oblivious enterprise that rolls the dice in the cyclic order ; in particular, it rolls every die equally many times. For , its expected total query count is uniformly bounded on .

The norm takes the maximum absolute value in the image of a function on . An enterprise is oblivious when it decides which dice to roll without depending on the outcomes so far, only "looking at" the outcomes after its last roll, when deciding what to return.

Stated more simply: functions that have a dice enterprise with tail on the query count are precisely the functions that are approximable by polynomials at a certain -dependent rate. Approximation theory studies, among other things, which functions are efficiently approximated by polynomials, so the paper's results relate approximation theory to probability theory.

In the language of imperfect-recall games: when a function from policies to scores in is sufficiently "approximable by polynomials", there is an imperfect-recall game with policy utilities and tail , and vice versa. In particular, we get "sandwiching" conditions (a necessary condition and a slightly stronger sufficient condition) for a policy-scoring function to be represented by an imperfect-recall game with a finite expected step count, uniform across all policies.

This is useful insofar as we want finite expected step counts and well-defined GT probabilities. The paper "Can CDT rationalise the ex ante optimal policy via modified anthropics?" is especially relevant: it represents ways a process can depend on the player's policy (e.g. how Omega in Newcomb's problem acts differently depending on the player's policy) using "modified anthropics", i.e. some fictitious imperfect-recall situation. In some cases, we can model such fictitious imperfect-recall situations as dice enterprises that implement some function corresponding to the dependence of the process on the policy.

Another possible application is designing RL algorithms that approximate KKT points of a score function. The basic idea is that we can convert an imperfect-recall game with into an RL environment whose expected total reward of a policy is , then use policy-gradient methods to seek stationary points of . Under certain regularity assumptions, these satisfy the KKT conditions of the -optimization problem, corresponding to CDT+GT policies of the imperfect-recall game. While the dice enterprises in the paper are not intended to be practically efficient, prior work gives practical algorithms for applying policy-gradient methods to non-standard policy score functions under certain assumptions (Zhang et al., Kumar et al.).

Examples

Let's consider some Bernoulli factory examples. First, let . This function satisfies , so it has a Bernoulli factory with tail bound , and therefore one with a uniformly bounded expected query count. By contrast, let . This function satisfies , so while it has a Bernoulli factory with tail bound , it has none with tail bound ; so by Markov's inequality, it has no Bernoulli factory with a uniformly bounded expected query count.

(For these rates: substituting turns on into on , whose best degree- approximation error is classically .)

We can interpret as a player's policy in an imperfect-recall game with only one possible observation and two possible actions given that observation. By the correspondence above, there is an imperfect-recall game with and uniformly bounded expected step count, and no imperfect-recall game with and uniformly bounded expected step count.

The upshot is that only sufficiently "smooth" or "polynomially approximable" policy-score functions have representing imperfect-recall games with a uniform bound on expected steps; and such uniform bounds imply well-defined GT probabilities. The aforementioned modified anthropics paper gets around this limitation by considering a sequence of increasingly good approximations to the decision problem by decision problems with a finite bound on the number of steps (and therefore, polynomial policy-score functions); GT probabilities can be defined at each stage, even when they cannot be defined globally.

I have explained why dice enterprises have some applications to decision theory, specifically imperfect-recall games. Whether or not these applications turn out to be useful, they are part of what got me thinking about the mathematical problem.

Why is it true?

Aside from the imperfect-recall motivation, why is the result true? It's easier to focus on the single-die case, since the multi-die case reduces to it. In particular: why is it that the dice enterprise tail bound is while the corresponding approximation bound is , where denotes the closed probability simplex of die weightings? Where does the factor of 2 come from?

A key concept is that any polynomial on the simplex can be written in the Bernstein basis, which consists of polynomials of the form , where is a vector of face counts summing to . These are the probabilities of the multinomial distribution: the probability that rolls of a -weighted die yield face counts . In the Bernoulli case, the Bernstein basis consists of the more familiar . A polynomial on the simplex is written in the degree- Bernstein basis as:

The coefficients are Bernstein coefficients. Conceptually, we are writing as the expected value of , where gives the face counts from rolling the -weighted die times.

The finite case is simple: a function from the simplex to has an oblivious enterprise making exactly rolls iff is a polynomial that can be written in the degree- Bernstein basis with all coefficients in . The corresponding enterprise rolls times, collects the face counts , and then flips fair coins to return 1 with probability .

Given a function which is not a polynomial but is approximable by polynomials, we could consider writing its polynomial approximations in the Bernstein basis. But some of these approximations will have negative Bernstein coefficients, making it harder to turn them into dice enterprises.

Conversely, suppose we have a dice enterprise for with uniform tail bound . Truncating the enterprise after rolls gives a polynomial of degree at most approximating with error . This immediately gives , which is worse than what we want. However, these approximating polynomials have Bernstein coefficients in , because they arise from probabilities of outcomes. The proof exploits this additional structure to obtain the stronger bound .

A useful intuition for the factor of 2 comes from statistical resolution. After flips of a coin with unknown bias , the observed proportion of heads has standard deviation , which is of order away from and . Near these endpoints, the relevant scale is instead . Polynomial approximation of degree has analogous resolution scales of order in the interior and near the endpoints. Thus samples correspond roughly to approximation degree , helping explain why a tail exponent corresponds to a polynomial approximation exponent . This extends to dice with more than two faces through the multinomial distribution. Making the intuition rigorous requires nontrivial approximation theory.

How I used AI

I will briefly discuss how I used AI for this paper. The main proof ideas came from ChatGPT, especially GPT-6-Astra-Pro. Here are two chat links: , (pasted text for the second is here). I also used Codex for Lean formalization of a previous version of the single-die result. Most of the work was not in getting the initial proof, but getting an understandable, clearly written proof. I did a lot of back-and-forth: discussing drafts with LLMs, writing my own draft content, asking for edits, etc. Some important editorial decisions on my part were about which results were worth including, and in which cases to cite previous literature to make proofs shorter. As usual in math, there is a tradeoff between longer but more elementary proofs and shorter proofs that rely more on existing literature.

AI is clearly very helpful for work like this, though the optimal collaborative workflow between humans and AIs is far from obvious? For this paper, I decided to post to arXiv early, especially because things are moving fast in AI and math. I have not decided on journal submission yet; I have considered ECP and EJP, although both have announced a pause on submissions while they re-evaluate their policies in light of how AI is changing math publishing.