The problem in Example 4.1 is that the discovery probability is so low that there is a probability bounded away from 0 that some action will not be discovered, no matter how many times a0 is played. The following theorem generalizes Example 4.1, giving a sufficient condition on the failure probability (which we later show is also necessary) that captures the precise sense in which the discovery probability is too low. Intuitively, the theorem says that if the DM is unaware of some acts that can improve her expected reward, and the discovery probability is sufficiently low, where "sufficiently low" means D(1, t) < 1 for all t and P∞
t=1 D(1, t) < ∞, then the DM cannot learn to play near-optimally. To make the theorem as strong as possible, we show that the lower bound holds even if the DM
has quite a bit of extra information, as characterized in the following definition.

Definition 4.2: Define a DM to be *quite knowledgeable* if
(in addition to S0, g0, D, R+, and R−) she knows S = S0, |A|, the transition function P0, the reward function R0 for states in S0 and actions in A0, and Rmax.

We can now state our theorem. It turns out that there are slightly different conditions on the lower bound depending on whether |S0| ≥ 2 or |S0| = 1.

Theorem 4.3: If D(1, t) < 1 for all t and P∞
t=1 D(1, t) <
∞, then there exists a constant c such that no algorithm can obtain within c *of the optimal reward for all MDPs that* are compatible with what the DM knows, even if the DM is quite knowledgeable, provided that |S0| ≥ 2, |A| > |A0|, and Rmax is greater than the reward of the optimal policy in the MDP (S0, A0, P0, R0)*. If* |S0| = 1, the same result holds if P∞
t=1 D(**j, t**) < ∞*, where* j = |A**| − |**A0|.

Proof: We construct an MDP M′′ = (S, A′′, g′′, P′′, R′′)
that is compatible with what the DM knows, such that no algorithm can obtain within a constant c of the optimal reward in M′′. The construction is similar in spirit to that of Example 4.1. Since |S| ≥ 2, let s1 be a state in S.

Let j = |A**| − |**A0|, let A′′ = A0 ∪ {a1**, . . . , a**j}, where a1**, . . . , a**j are fresh actions not in A0, let g
′′ be such that g
′′(s1) = g0(s1) ∪ {a1}, g
′′(s) = A′′, for s 6= s1. That is, there is only one action that the DM is not aware of in state s1, while in all other states, she is unaware of all actions in A − A0. Let P
′′(s1, s1, a1) = P
′′(s, s1, a**) = 1**
for all a ∈ A′′ − A0 and s ∈ S (note that P
′′ is determined by P0 in all other cases). It is easy to check that M′′ is compatible with what the DM knows, even if the DM knows that S = S0, knows |A|, and knows Rmax.

Let R′′(s1, s1, a1) = R′′(s, s1, a) = Rmax for all s 6= s1 and a ∈ A − A0 (R′′ is determined by R0 in all other cases). By assumption, the reward of the optimal policy in
(S0, A0, g0, P0, R0) is less than Rmax, so the optimal policy is clearly to get to state s1 and then to play a1 (giving an average reward of Rmax per time unit). Of course, doing this requires learning a1.

As in Example 4.1, we first prove that for M′′ there exists a constant d > 0 such that, with probability d, no algorithm will discover action a1 in state s1.

Again, we have

$$\begin{array}{r c l}{{P r(E_{t,s_{1}})}}&{{=}}&{{\prod_{t^{\prime}=1}^{t}(1-D(1,t^{\prime})).}}\end{array}$$

Since P∞
t=1 D(1, t) < ∞, we must have that limt→∞ D(1, t**) = 0**. Since D(1, t) < 1 for all t, there must exist a constant c1 < 1 such that D(1, t) < c1 for all t. If c1 = 0, then D(1, t**) = 0** for all t ≥ 1 (since D(1, t) ≤
c1 by assumption, and D(1, t) ≥ 0, since it is a probability), so Pr(Et,s1
**) = 1**, and we can take d = 1. If c1 > 0, then we show below that 1 − D(1, t′) ≥ (1 − c1)
D(1,t′)/c1
.

Thus, we get that

$$\begin{array}{r c l}{{\mathrm{Pr}(E_{t,s})}}&{{\geq}}&{{\prod_{t^{\prime}=1}^{t}(1-c_{1})^{D(1,t^{\prime})/c_{1}}}}\\ {{}}&{{\geq}}&{{(1-c_{1})^{\sum_{t^{\prime}=1}^{t}D(1,t^{\prime})/c_{1}}.}}\end{array}$$
$=\sum_{n=0}^{\infty}D(1,t!)-1$ $=\sum_{n=0}^{\infty}D(1,t!)$

```
Since, by assumption, P∞
                        t
                        ′=1 D(1, t′) < ∞, we can take
d = (1 − c1)
            P∞
              t
               
               ′=1
                 
                  D(1,t′)/c1
                          .

```

It remains to show that 1 − D(1, t′) ≥ (1 − c1)
D(1,t′)/c1
.

Since 0 ≤ D(1, t′) ≤ c1 < 1, it suffices to show that 1 − x ≥ (1 − b)
x/b = e
(x/b**) ln(1**−b)for 0 ≤ x ≤ b < 1.

Let g(x**) = 1** − x − e
(x/b**) ln(1**−b). We want to show that g(x) ≥ 0 for 0 ≤ x ≤ b < 1. An easy substitution shows that g(0) = g(b**) = 0**. Differentiating g, we get that g
′(x) = −1 −
ln(1−b)
be
(x/b**) ln(1**−b), and g
′′(x) =
−
ln(1−b)
2 b 2 e
(x/b**) ln(1**−b) < 0. Since g(0) = g(b**) = 0** and g is concave, we must have g(x) = g((1−x/b)0+(x/b)b) ≥
(1 − x/b)g(0) + (x/b)g(b**) = 0** for x ∈ [0, b], as desired.

Let r2 be the expected reward of the optimal policy in M′′,
and let r1 be the expected reward of the optimal policy in the MDP (S, A′′ − {a1}, P′′|A−{a1}, R′′|A−{a1}). As we have observed, r2 > r1. With probability at least d, no algorithm will discover a1, so the DM will know at most the actions in A′′ − {a1}, and cannot get a reward higher than r2. Thus, no algorithm can give the DM an expected reward higher than (1 − d)r1 + dr2. Thus, we can take c = d(r1 − r2). If |S0| = 1, essentially the same argument holds. We again construct an MDP M′′ = (S0, A′′, g′′, P′′, R′′). Since |S0| = 1, all components of M′′ are determined except for R′′. We take R′′(s1, s1, a1) = Rmax, and R′′(s1, s1, a) = Rmax − 1, for a ∈ A′′ − (A0 ∪ {a1}). Again, the unique optimal policy is to play a1 at all times, so the problem reduces to learning a1. Without further assumptions, all we can say is that this probability of learning a1 after t steps of exploration is at most D(**j, t**), so we must replace D(1, t)
by D(**j, t**) in the argument above. 4 4We remark that we can still use D(1, t) if the DM does know that S = S0, but does not know |S|, and |S| ≥ 2. We can also use D(1, t) if the probability of learning the specific action a1 after t steps of exploration is D(1, t).