MDPUs among the M∗family. The DM knows that she is in a member of the M∗family, but she does not know which. We now show that whether an upper bound of the number of actions being given to the DM makes a big difference to her performance.

For all state s that has at least one new action, assume there are js actions unaware to the DM (note that the DM does not know the value of js), we have

$$\begin{array}{r c l}{{P r(E_{t,s})}}&{{=}}&{{\prod_{t^{\prime}=1}^{t}(1-\frac{1}{j_{s}+t})}}\\ {{}}&{{=}}&{{(\frac{j_{s}}{j_{s}+1}\times\frac{j_{s}+1}{j_{s}+2}\times\frac{j_{s}+2}{j_{s}+3}\times\cdots\frac{j_{s}+t-1}{j_{s}+t})}}\\ {{}}&{{=}}&{{\frac{j_{s}}{t+j_{s}}.}}\end{array}$$

First, assume that the DM knows k - an upper bound on the actual number of actions in the underlying MDPU. Thus k ≥ js, and

$$\begin{array}{r c l}{\operatorname*{Pr}(E_{t,s})}&{\leq}&{{\frac{k}{t_{s}+k}}.}\end{array}$$

Take t =
(1−δ)k δ, we get Pr(Et,s) ≤ δ. Thus, if the DM
knows k, she is guaranteed to discover all actions with probability ≥ (1 − δ) for any δ > 0 in time polynomial in k and 1/δ no matter which game she is playing. It follows easily that she is also guaranteed to achieve the optimal reward with probability ≥ (1 − δ) for any δ > 0 in polynomial time.

Now suppose the DM does not know k. We shall prove that the DM cannot obtain an optimal reward no matter how many times a0 is played. Suppose the highest reward she could get from any currently discovered action is r, and suppose she has played a0 for t > 0 times without finding any new actions. Since the underlying MDPU
can be any member of the M∗family, let it be Mi where i **= max(9**t, 10r). Thus, the optimal reward is i ≥ 10r, which is 10 times of what the DM has currently achieved.

We now show that this actually happens with constant probability.

$$\begin{array}{r c l}{{P r(E_{t,s})}}&{{=}}&{{\frac{i}{t+i}}}\\ {{}}&{{\geq}}&{{\frac{9t}{t+9t}}}\\ {{}}&{{=}}&{{\frac{9}{10}.}}\end{array}$$

In this case with probability ≥ 9 10 the DM only attains 1 10 of the optimal reward. In fact, we can set i = max(**nt, nr**+r) with arbitrarily large n, in which case with probability ≥
n n+1 the DM only attains 1 n+1 of the optimal reward.

In conclusion, if the DM does not know k, she can attain an arbitrarily low reward compared to the optimal reward no matter how many times she plays a0. On the other hand, if she knows k, she is guaranteed to achieve a near-optimal reward in polynomial time.

## 5 Learning To Play Near-Optimally

In this section, we show that a DM can learn to play near-optimally in an MDPU where P∞
t=1 D(1, t) = ∞.

Moreover, we show that when P∞
t=1 D(1, t) = ∞, the speed at which D(1, t) decreases determines how quickly the DM can learn to play near-optimally. Specifically, if PT
t=0 D(1, t) ≥ m1f(ln T ) + m2 for all T > 0 for constant m1 > 0 and m2, and an invertible function f, then the DM can learn to play near-optimally in time polynomial in f
−1(1/δ). In particular, if f is the identity (so that PT
t=0 D(1, t) ≥ m1 ln T + m2), then the DM can learn in time polynomial in 1/δ (and, as we shall see, in time polynomial in all other parameters of interest). We call the learning algorithm URMAX, since it is an extension of RMAX to MDPUs. While the condition P∞
t=1 D(1, t) =
∞ may seem rather special, in fact it arises in many applications of interest. For example, when learning to fly a helicopter [1, 19], the space of potential actions in which the exploration takes place, while four dimensional (resulting from the six degree of freedom of the helicopter), can be discretized and taken to be finite. Thus, if we explore by examining the potential actions uniformly at random, then D(1, t) is constant for all t, and hence P∞
t=1 D(1, t) = ∞.

Indeed, in this case PT
t=1 D(1, t) is O(T ), so it follows from Corollary 5.5 below that we can learn to fly the helicopter near-optimally in polynomial time. The same is true in any situation where the space of potential actions in which the exploration takes place is finite and understood.

We assume throughout this section that P∞
t=1 D(1, t) =
∞. We would like to use an RMAX-like algorithm to learn to play near-optimally in our setting too, but there are two major problems in doing so. The first is that we do not want to assume that the DM knows |S|, |A|, or Rmax. We deal with the fact that |S| and |A| are unknown by using essentially the same idea as Kearns and Singh use for dealing with the fact that the true ǫ-mixing time T is unknown:
we start with an estimate of the value of |S| and |A|, and keep increasing the estimate. Eventually, we get to the right values, and we can compensate for the fact that the payoff return may have been too low up to that point by playing the policy sufficiently often. The idea for dealing with the fact that Rmax is not known is similar. We start with an estimate of the value of Rmax, and recompute the value of K1(T ) and the approximating MDP every time we discover a transition with a reward higher than the current estimate. (We remark that this idea can be applied to RMAX as well.) The second problem is more serious: we need to deal with the fact that not all actions are known, and that we have a special *explore* action. Specifically, we need to come up with an analogue of K1(T ) that describes how many times we should play the explore action a0 in a state s, with a goal of discovering all the actions in s. Clearly this value will depend on the discovery probability (it turns out that all we need to know is D(1, t) for all t) in addition to all