(a) With probability at least 1−δ/4, every action that can be played in a state s ∈ Sr is discovered (i.e., is in gr(s)).

(b) If all actions that can be played in s ∈ Sr are discovered, then with probability at least 1 − δ/4, Pr is close to P; specifically, |Pr(s, s′, a) − P(s, s′, a)| ≤
ǫ 4NT Rmax for all **s, s**′ ∈ Sr, a ∈ gr(s).

(c) Sr contains all the "significant" states in S; if (a)
and (b) hold, with probability at least 1 − δ/4, Opt(Mr, ǫ, T ) ≥ Opt(**M, ǫ, T** ) − 2ǫ.
Part (a) is immediate from Lemma 5.1 and the fact that |Sr| ≤ N. Parts (b) and (c) are similar to the arguments given by Brafman and Tennenholtz, so we defer the details to the full paper. The desired result now follows using techniques similar in spirit to those used by Brafman and Tennenholtz [3]; we leave the details to the full paper.

We get URMAX(S0, g0**, D, ǫ, δ, s**0) by running URMAX(S0, g0, D, N, k, Rmax**, T, ǫ, δ, s**0) using larger and larger values for N, k, Rmax, and T . Sooner or later the right values are reached. Once that happens, with high probability, the policy produced will be optimal in all later iterations. However, since we do not know when that happens, we need to continue running the algorithm. We must thus play the optimal policy computed at each iteration enough times to ensure that, if we have estimated N, k, Rmax, and T correctly, the average reward stays within 2ǫ of optimal while we are testing higher values of these parameters. For example, suppose that the actual values of these parameters are all 100. Thus, with high probability, the policy computed with these values will give an expected payoff that is within 2ǫ of optimal. Nevertheless, the algorithm will set these parameters to 101 and recompute the optimal policy. While this recomputation is going on, it may get low reward (although, eventually it will get close to optimal reward). We need to ensure that this period of low rewards does not affect the average.

URMAX(S0, g0**, D, ǫ, δ, s**0):

Set N := |S0|, k := |A0|, Rmax := 1, T **:= 1**
Repeat forever Run URMAX((S0, g0, D, N, k, Rmax**, T, ǫ, δ, s**0)
if no inconsistency is discovered then run the policy computed by URMAX((S0, g0, D, N, k, Rmax**, T, ǫ, δ, s**0) for K2 + K3 steps, where where K2 = 2(N k max(K1(T + 1), K0)) 32 Rmax/ǫ K3 = (2Rmax + 1) max(( 2Rmax ǫ)
3, **8 ln(** 4 δ
)
3)/ǫ N := N + 1; k := k + 1, Rmax := Rmax + 1, T := T + 1.
The following theorem shows that URMAX(S0, g0**, D, ǫ, δ, s**0) is correct. (The proof, which is deferred to the full paper, explains the choice of K2 and K3.)
Theorem 5.3: *For all MDPs* M = (**S, A, g, P, R**) compatible with S0 and g0, if the ǫ*-return mixing time of* M is TM, then for all states s0 ∈ S0*, with probability at least* 1 − δ*, for all states* s0 ∈ S0, URMAX(S0, g0**, D, ǫ, δ, s**0) computes a policy π**ǫ,δ,T**M,s0 such that, for a time t**M,ǫ,δ**
that is polynomial in |S|, |A|, TM, 1/ǫ, and K0*, and all* t ≥ t**M,ǫ,δ***, we have* UM (s0, π, t) ≥ Opt(**M, ǫ, T**M) − 2ǫ.

Thus, if P∞
t=1 D(1, t) = ∞, the DM can learn to play near-optimally. We now get running time estimates that essentially match the lower bounds of Theorem 4.4.

Proposition 5.4: If PT
t=1 D(1, t) ≥ f(T )*, where* f :
[1, ∞] → IR is an increasing function whose co-domain includes (0, ∞]*, then* K0 ≤ f
−1(ln(4N/δ))*, and the running time of* URMAX *is polynomial in* f
−1(ln(4N/δ)).

Proof: Immediate from Theorem 5.3 and the definition of

## K0.

Recall from Theorem 5.2 that if PT
t=1 D(1, t) ≤ f(T ), the no algorithm that learns near-optimally can run in time less than f
−1(c
′**ln(1**/δ)) (where c
′ = c/ **ln(1**/(1 − c))), so we have proved an upper bound that essentially matches the lower bound of Theorem 5.2.

Corollary 5.5: If PT
t=1 D(1, t) ≥ m1 ln(T ) + m2 *(resp.,*
PT
t=1 D(1, t) ≥ m1 ln(ln(T **) + 1) +** m2) for some constants m1 > 0 and m2*, then the DM can learn to play nearoptimally in polynomial time (resp., exponential time).*
Proof: If f(T ) = m1 ln(T ) + m2, then as we have observed, f
−1(t) = e
(t−m2)/m1
, so f
−1(ln(4N/δ) =
e
−m2/m1 (4N)
1/m1
· (1/δ)
1/m1
. Thus, f
−1(ln(4N/δ) has the form a(1/δ)
1/m1
, and is polynomial in 1/δ. The result now follows from Theorem 5.2. The argument is similar if PT
t=1 D(1, t) ≥ m1 ln(ln(T **) + 1) +** m2; we leave details to the reader.

## 6 Conclusion

We have defined an extension of MDPs that we call MDPUs, Markov Decision Processes with Unawareness, to deal with the possibility that a DM may not be aware of all possible actions. We provided a complete characterization of when a DM can learn to play near-optimally in an MDPU, and have provided an algorithm that learns to play near-optimally when it is possible to do so, as efficiently as possible. Our methods and results thus provide guiding principles for designing complex systems. We believe that MDPUs should be widely applicable. We hope to apply the insights we have gained from this theoretical analysis to using MDPUs in practice, for example,