The environment. We define the environment, denoted by µ, in a similar way. Specifically, for any k ∈ N the probability of okrk, given the current interaction history o1r1a1o2r2a2 **. . . o**k−1rk−1ak−1, is given by the probability measure µ(okrk|o1r1a1o2r2a2 **. . . o**k−1rk−1ak−1). For the moment we will not place any further restrictions on the environment.

3.2 Example. To illustrate this formalism, consider again the Two Coins Game introduced in Example 3.1. Let P := {0, 1, 2}×{0, 1} be the perception space representing the number of heads after tossing the two coins and the value of the received reward. Likewise let A := {0, 1, 2} be the action space representing the agent's guess at the number of heads that will occur. Assuming two fair coins, we can represent this environment by µ:

$$\mu(o_{k}r_{k}|o_{1}\ldots a_{k-1}):=\left\{\begin{array}{l}{{\frac{1}{4}}}\\ {{\frac{3}{4}}}\\ {{\frac{1}{2}}}\\ {{\frac{1}{2}}}\\ {{0}}\end{array}\right.$$
$$\begin{array}{l}{{\mathrm{if~}o_{k}=a_{k-1}\in\{0,2\}\wedge r_{k}=1,}}\\ {{\mathrm{if~}o_{k}\neq a_{k-1}\in\{0,2\}\wedge r_{k}=0,}}\\ {{\mathrm{if~}o_{k}=a_{k-1}=1\wedge r_{k}=1,}}\\ {{\mathrm{if~}o_{k}\neq a_{k-1}=1\wedge r_{k}=0,}}\\ {{\mathrm{otherwise.}}}\end{array}$$

An agent that performs well in this environment would be,

$$\pi\big(a_{k}|o_{1}r_{1}a_{1}\ldots o_{k}r_{k}\big):={\left\{\begin{array}{l l}{1}&{{\mathrm{for~}}a_{k}=1,}\\ {0}&{{\mathrm{otherwise.}}}\end{array}\right.}$$

That is, always guess that one head will be the result of the two coins being tossed. A more complex agent might keep count of how many heads occur in each cycle and then adapt its strategy if it seems that the coins are sufficiently biased. Measure of success. Our next task is to formalise the idea of "profit" or "success" for an agent. Informally, we know that the agent must try to maximise the amount of reward it receives, however this could mean several different things. For example, one agent might quickly find a way to get a reward of 0.9 in every cycle. After 100 cycles it will have received a total reward of about 90 with an average reward per cycle of close to 0.9. A second agent might spend the first 80 cycles exploring different actions and their consequences, during which time its average reward might only be 0.2. Having done this exploration however, it might then know a way to get a reward of 1.0 in every cycle. Thus after 100 cycles its total reward is only 80×0.2 + 20.0 = 36, giving an average reward per cycle of just 0.36. After 1,000 cycles however, the second agent will be performing much better than the first.

Which agent is the better one? The answer depends on how we value reward in the near future versus reward in the more distant future. In some situations we may want our agent to perform well fairly quickly, in others we might only care that it eventually reaches a level of performance that is as high as possible.

A standard way of formalising this is to scale the value of rewards so that they decay geometrically into the future at a rate given by a discount parameter γ ∈ (0, 1). For example, with γ = 0.95 a reward of 0.7 that is 10 time steps into the future would be given a value of 0.7 × (0.95)10 ≈ 0.42. At 100 time steps into the future a reward of 0.7 would have a value of just over 0.004. By increasing γ towards 1 we weight long term