# Pseudo-random sequence prediction

Disclaimer: I posted this question on CS about a month ago, but haven't gotten any response, despite positive rating. It has been suggested that I repost the question on CV, so here goes.

Imagine there is an agent, who makes binary decisions. And an environment, which, for each of the agent's decisions ("trials"), either rewards the agent or not. The criteria for rewarding the agent's decisions are not simple. In general criteria are random, but they have limitation, for example, environment never rewards more than 3 times for the same decision and never alternates rewarded decision more than 4 times in a row.

Sequence of criteria might look something like this then

0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 ...


but never

0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 ...


because reward criterion cannot repeat more than 3 times.

In these conditions it is quite easy to formulate the strategy ideal observer should undertake to maximize the reward. Something along the lines of

1. decide randomly
2. if you detect that criteria repeated 3 times -- decide opposite than last criterion
3. if you detect that criteria alternated 4 times, decide according to the last criterion

Now, the difficult part. Now the criterion on each trial depends not only on the history of previous criteria, but also on the history of agent's decisions, e.g. if agent alternates on more than 8 out of the last 10 trials, reward same decision as agent made last time (as if to discourage the agent from alternating) and if agent repeated same decision on more than 8 of the the last 10 trials, i.e. he is biased, make criterion opposite of the bias. The priority of history of criteria over history of decisions is specified in advance, so there is never ambiguity.

The sequences of decisions (d) and criteria (c) might now look like this

d: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 ...
c: 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 ...
↑ here criteria counteract bias in decisions


I do not see any simple way of inventing maximizing strategy for the agent. But I am sure there must be one, and some kind of clever machine learning algorithm should be able to identify it.

My question is not so much about how to solve this problem (although I would be happy if you suggest a solution), but more how these types of problems are called? Where can I read about it (the more specific, the better)? In general, how can I, as a biologist, approach this type of problem?

• sounds like a good candidate for game theory – MikeP Jan 5 '16 at 19:24

I see no reason you couldn't formalize this as a discrete Markov decision process, a fundamental tool in reinforcement learning. MDPs are fully specified when one knows:

• $S:$ a set of states
• $A:$ a set of actions, sometimes indexed by state
• $T(s,a,s'):$ a transition function giving the probability of arriving in state $s'$ from state $s$ having taken action $a$
• $R(s,a,s')$: a reward function
• $\gamma$: a discount factor

What you call a "strategy" is the optimal policy, a function mapping states to actions, often written $\pi(s)$.

Importantly, MDPs are memoryless: The probability of transitioning to a given state depends only on the current state and the actions available. This may seem at odds with the memory of your environment, but it's no obstacle, so long as your current state accounts for all relevant information of prior states. Put another way, the present must recall all relevant history.

In your example, that means that each state must account for (1) up to 10 prior agent decisions (2) up to five prior reward criteria. You'd have a large state space, each state corresponding to the trails observed. (If I made no errors on the back of my envelope, you'd have just under 65,000 states.)

As for how the environment decides the reward criterion based on trails of alternations or repeat decisions, it can be formalized as part of the transition function. Knowing all that, you could then find the optimal policy through planning algorithms like value iteration or policy iteration.

For some useful resources, you might start with Michael Brown's dissertation. If you can program or are willing to learn, you might look at BURLAP, a reinforcement learning library for Java.