# Pseudo-random sequence prediction

Disclaimer: I am a biologist, so sorry for (perhaps) basic question phrased in such crude terms.

I am not sure if I should ask this question here or on DS/SC, but CS is the largest of three, so here goes. (After I posted, it occurred to me that Cross-Validated might be the better place for it, but alas).

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? Is there an abstract solution or only simulation can help? In general, how can I, as a biologist, approach this type of problem?

• see eg autoregressive time series analysis. it would help if you were more detailed about the input data. is it from biology? there are std techniques for std problems. recurrent ANNs (artificial neural nets) also handle this. also maybe drop by Computer Science Chat – vzn Dec 13 '15 at 1:47
• Hidden Markov models may be a useful tool. – Raphael Dec 14 '15 at 9:07
• You may want to read up on Follow-The-Leader and other variants - onlineprediction.net/?n=Main.FollowTheLeader – MotiN Dec 14 '15 at 14:39
• I think what you are referring to is close to what people in ML call Reinforcement Learning. – Kaveh Jan 3 '16 at 8:31
• ps: You may want to try posting on Cross Validated if you don't get an answer here after some time. – Kaveh Jan 3 '16 at 8:32