We introduce a learning framework that combines elements of the well-known PAC and mistake-bound models. The KWIK (knows what it knows) framework was designed particularly for its utility in learning settings where active exploration can impact the training examples the learner is exposed to, as is true in reinforcement-learning and activelearning problems. We catalog several KWIK-learnable classes as well as open problems, and demonstrate their applications in experience-efficient reinforcement learning. Kakade et al. 2003; Strehl et al. 2006a Strehl et al. , 2007 lies the idea of distinguishing between instances that have been learned with sufficient accuracy and those whose outputs are still unknown. The Rmax algorithm (Brafman and Tennenholtz 2002) , for example, estimates transition probabilities for each state-action-next-state triple of a Markov decision process. The estimates are made separately, as licensed by the Markov property, and the accuracy of the estimate is bounded using Hoeffding bounds. The algorithm explicitly distinguishes between probabilities that have been estimated accurately (known) and those for which more experience will be needed (unknown). By encouraging the agent to gather more experience in the unknown states, Rmax can guarantee a polynomial bound on the number of timesteps in which it has a non-near-optimal policy (Kakade 2003) . In this paper, we make explicit the properties that are sufficient for a learning algorithm to be used in efficient exploration algorithms like Rmax. Roughly, the learning algorithm needs to make only accurate predictions, although it can opt out of predictions by saying "I don't know" (⊥). However, there must be a (polynomial) bound on the number of times the algorithm can respond ⊥. We call such a learning algorithm KWIK ("know what it knows"). Section 2 provides a motivating example and sketches possible uses for KWIK algorithms. Section 3 defines the KWIK conditions more precisely and relates them to established models from computational learning theory. Sections 4-6 survey a set of hypothesis classes for which KWIK algorithms can be created. Section 7 describes a number of applications of KWIK in reinforcement learning, focusing on unifying existing results as well as providing a new algorithm for factored-state Markov decision processes. Section 8 concludes the paper and lists a few important open problems. The research described in this paper builds upon and extends the work presented at the Twenty-Fifth International Conference on Machine Learning ) and in Advances in Neural Information Processing Systems 20 (Strehl and Littman 2008). Consider the simple navigation task in Fig. 1 . There is a set of nodes connected by edges, with the node on the left as the source and the dark one on the right as the sink. Each edge in the graph is associated with a binary cost vector of dimension n = 3, indicated in the figure. The cost of traversing an edge is the dot product of its cost vector with a fixed weight vector θ = [1, 2, 0]. Assume that θ is not known to the agent, but the graph topology and all cost vectors are. In each episode, the agent starts from the source and moves along some path to the sink. Each time it crosses an edge, the agent observes its true cost. The cost of a path from the source to the sink is the sum of edge costs along the path. Once the sink is reached, the next episode begins. Through navigating in the graph, the agent tries to identify an optimal path with minimum cost while taking a suboptimal path in as few episodes as possible. There are 3 distinct paths in this example. Given the θ value above, the top has a cost of 12, the middle 13, and the bottom 15. A simple approach for this task is for the agent to assume edge costs are uniform and walk the shortest (middle) path to collect data. It would gather 4 examples of [1, 1, 1] → 3 and one of [1, 0, 0] → 1. Standard regression algorithms could use this dataset to find aθ that fits this data perfectly. However, there may be severalθ s supported by the available data. Here, the least-squares solution,θ = [1, 1, 1], is a natural choice. The learned weight vector could then be used to estimate costs for the three paths: 14 for the top, 13 for the middle, 14 for the bottom. Using these estimates, an agent would continue to take the middle path forever, never realizing it is not optimal. In contrast, consider a learning algorithm that "knows what it knows". Instead of creating an approximate weight vectorθ , it reasons about whether the costs for each edge can be obtained from the available data. The middle path, since all its edge costs have been observed, is definitely 13. The last edge of the bottom path has cost vector [0, 0, 0], so its cost must be zero, but the penultimate edge of this path has cost vector [0, 1, 1]. This vector is a linear combination of the two observed cost vectors, so, regardless of θ , its cost is which is just 3 − 1 = 2. Thus, the agent knows the bottom path's cost is 14-worse than the middle path. The vector [0, 0, 1] on the top path is linearly independent of the observed cost vectors, so its cost is undecided. We know we don't know. A safe thing to assume provisionally is that the cost is zero-the smallest possible cost, encouraging the agent to try the top path in the second episode. Now, it observes [0, 0, 1] → 0, allowing it to solve for θ exactly (θ = [1, 2, 0]) and accurately predict the cost for any vector (since the training data spans n ). It now knows that it knows all the costs, and can confidently take the optimal (top) path. In general, any algorithm that guesses a weight vector may never find the optimal path. An algorithm that uses linear algebra to distinguish known from unknown costs will either take an optimal route or discover the cost of a linearly independent cost vector on each episode. Thus, it can never choose suboptimal paths more than n times. Formal discussions of learning noise-free linear functions are provided in Sect. 4.2. In contrast, an agent that does not generalize, but visits every edge to learn its cost, will require m episodes to learn optimal behavior, in the worst case, where m is the number of edges in the graph. This example shows how combining generalization with explicitly distinguished known and unknown areas can lead to efficient and optimal decision algorithms. The motivation for studying KWIK learning grew out of its use in sequential decision making problems like this one. However, other machine-learning problems could benefit from this perspective and from the development of efficient algorithms. For instance, action selection in bandit problems (Fong 1995a) and associative bandit problems (Strehl et al. 2006c ) (bandit problems with inputs) can both be addressed in the KWIK setting by choosing the better arm when both payoffs are known and an unknown arm otherwise. KWIK could also be a useful framework for studying active learning (Cohn et al. 1994 ) and anomaly detection (Lane and Brodley 2003) , both of which are machine-learning problems that require some degree of reasoning about whether a recently presented input is predictable from previous examples. When mistakes are costly, as in utility-based data mining (Weiss and Tian 2006) or learning robust control (Bagnell et al. 2001) , having explicit predictions of certainty can be very useful for decision making. Two parties are involved in a KWIK learning protocol. The learner runs a learning algorithm and makes predictions; while the environment, which represents an instance of a KWIK learning problem, provides the learner with inputs and observations. The protocol for a KWIK "run" is as follows: -The hypothesis class H, accuracy parameter , and confidence parameter δ are known to both the learner and the environment. -The environment selects a target function h * adversarially. -The environment selects an input x t ∈ X adversarially and informs the learner. The target value y t = h * (x t ) is unknown to the learner. -The learner predicts an outputŷ t ∈ Y ∪ {⊥}. We callŷ t valid ifŷ = ⊥. -Ifŷ t = ⊥, the learner makes an observation z t ∈ Z of the output. In the deterministic case, z t = y t , but generally the relation between z t and y t is problem specific. For example, z t = 1 with probability y t and 0 with probability 1 − y t in the Bernoulli case, and z t = y t + η t for a zero-mean random variable η t in the additive noise case. Definition 1 Let H ⊆ (X → Y) be a hypothesis class. We say that H is KWIK-learnable if there exists an algorithm A with the following property: for any 0 < , δ < 1, the following two requirements are satisfied with probability at least 1 − δ in a whole run of A according to the KWIK protocol above: We call A a KWIK algorithm and B( , δ, dim(H)) a KWIK bound of A. We will also use B( , δ) for simplicity, if there is no ambiguity. Furthermore, H is efficiently KWIK-learnable if the per-timestep time complexity of A is polynomial in 1/ , 1/δ, and dim(H). 1 Here, |ŷ − y| may be any nonnegative-valued function that measures the discrepancy or distance between y and y. To simplify notation, we have used the operator "−" in a broad sense and it is not restricted to algebraic subtraction. For instance: (i) in the special situation of Y ⊆ , as is considered in many cases of this paper, | · | is understood as the absolute value; (ii) when Y ⊆ k , | · | may mean vector norm; and (iii) when y andŷ are probability distributions, | · | may be used for total variation. Mach Learn (2011) 82: 399-443 403 Fig. 2 Relationship of KWIK to a variant of the PAC and the MB frameworks in terms of how labels are provided for inputs A few notes are in order. First, the accuracy requirement in Definition 1 considers the "realizable" case only; namely, the target function is assumed to be in the hypothesis class. In contrast, the sample-complexity requirement has to hold even in the "unrealizable" case where h * / ∈ H. Second, all KWIK algorithms provided in this paper enjoy polynomial time complexity and thus are efficient. We note that a KWIK algorithm can be randomized, and so the confidence parameter, δ, may be necessary even in deterministic problems. Third, the definition above allows the hypothesis class H to be infinite. In this case, we must require the KWIK bound to be polynomial in the complexity measure, dim(H), rather than in the size of H. While in some situations (such as in Sect. 5) dim(H) is straightforward to define, it remains an open question what measure would be appropriate for KWIK in general. More discussions are in Sect. 5. Figure 2 illustrates the relationship of KWIK to the similar PAC (Probably Approximately Correct) (Valiant 1984) and MB (Mistake Bound) (Littlestone 1987) frameworks. In all three cases, a series of inputs (instances) is presented to the learner. Each input is depicted in the figure by a rectangular box. In the PAC model, inputs are drawn from a fixed distribution, and the learner is provided with labels (correct outputs) for an initial sequence of i.i.d. inputs, depicted by shaded rectangles. After that point, the learner is required to produce a hypothesis that, with probability at least 1 − δ, makes accurate predictions for 1 − fraction of inputs. For the purpose of the present paper, it is natural to consider a variant of PAC, where the learner is required to produce an -accurate outputs (empty boxes) for all new inputs with probability at least 1 − δ. In the MB model, the learner is expected to produce an output for every input. Labels are provided to the learner whenever it makes a mistake (filled boxes). Inputs are selected adversarially, so there is no bound on when the last mistake might be made. However, MB algorithms guarantee that the total number of mistakes is small, so the ratio of incorrect to correct outputs must go to zero asymptotically. In the most widely studied concept learning problem, any MB algorithm for a hypothesis class can be used to provide a PAC algorithm for the same class (Littlestone 1989), 2 but the reverse is not necessarily true (Blum 1994). The KWIK model has elements of both PAC and MB. Like PAC, a KWIK algorithm has tolerance parameters allowing for some failures. Like MB, inputs to a KWIK algorithm 2 An extension from concept learning to real-valued function learning is given by Klasner and Simon (1995) . Mach Learn (2011) 82: 399-443 may be selected adversarially. Instead of bounding mistakes, a KWIK algorithm must have a bound on the number of label requests (⊥) it can make. By requiring performance to be independent of how inputs are selected, a KWIK algorithm can be used in cases in which the input distribution is dependent in complex ways on the KWIK algorithm's behavior, as can happen in on-line or active learning settings. Any KWIK algorithm can be turned into a MB algorithm with the same bound by simply having the algorithm guess an output each time it is not certain; the KWIK bound is automatically an upper bound of the number of mistakes. However, some hypothesis classes are exponentially harder to learn in the KWIK setting than in the MB setting. An example is conjunctions of n Boolean variables, in which MB algorithms can guess "false" when uncertain and learn with n + 1 mistakes, but a KWIK algorithm may need (2 n ) many ⊥s to acquire the negative examples required to capture the target hypothesis: a concrete sequence of adversarial input is given in Li (2009), and a related lower bound is obtained by Angluin (1988) for the "double sunflower" lemma in the query-based learning model. The separation is not only theoretically important, but illustrates an important differences in the allowable behavior and cost of information for MB and KWIK. In both MB and KWIK, we can consider the learning process as a two-player game where at even depth nodes of the game tree the adversary picks a new input and a label for the last input that must be consistent with the nodes above it. At the odd nodes, the learner gets to make a prediction. The game terminates when the odd player has formed the correct hypothesis and the payout is determined as follows. For MB, the payout is the negative of the number of mistakes predictions along the trajectory. For KWIK, the payout is −B( , δ, dim(H)), based on the number of ⊥s on the chosen trajectory in the game tree, plus −∞ for any trajectory that contains a mistaken (with probability at least δ) prediction. Notice that structurally the MB tree and the KWIK tree are virtually identical (except for the ⊥ action), but that their payout structures will induce very different behavior. For instance, in the case of learning a conjunction, if the adversary chooses a positive example, future trajectories (assuming the adversary plays rationally) in both the MB and KWIK tree will be exponentially smaller than under the corresponding negative example, which provides very little information. However, an optimal agent in the MB tree can mitigate cost on these long (negative) trajectories by always selecting "false" when it does not have evidence that the chosen input is true. This will either cost it a single mistake but put it on a very short branch (getting a highly informative positive example), or cost it nothing but put it on a very long (but not costly) path. On the other hand, the optimal agent in the KWIK game tree does not have the option of hedging its bets. Where mistakes were made in the MB tree with only a local unit cost, in the KWIK tree the payout structure makes them infinitely expensive. The only guaranteed finite payout available to the agent comes from choosing ⊥ on every input with uncertain output, and there are exponentially many of these as the adversary can force the agent down one of the longer (negative example only) paths. Intuitively, the MB agent can declare its intentions after the adversary announces the label. If it correctly predicted a negative example, MB "knew it all the time". If it was wrong, it made a highly informative mistake. In contrast, the KWIK agent cannot engage in such self deception. To avoid the −∞ payout, it must only make valid predictions when it is absolutely certain of the outcome. The benefit of this restriction, is that unlike the MB agent, the KWIK agent is intrinsically "self aware": before it makes a prediction, it can always categorize the step as "exploration" (⊥) or "exploitation" (label), while the MB algorithm inherently relies on making such distinctions after the fact. While such devotion to certainty may seem too restrictive, we argue in Sect. 7.3 that the lack of assumptions and self awareness in KWIK is a better fit than either MB or PAC for creating sample-efficient reinforcement learning algorithms. Mach Learn (2011) 82: 399-443 405 3.3 Other online-learning models The notion of allowing the learner to opt out of some inputs by returning ⊥ is not unique to KWIK. Several other authors have considered related models: -Sleeping Experts (Freund et al. 1997a ) can respond ⊥ for some inputs, although they need not learn from these experiences and the number of ⊥s in the whole run may be unbounded; -Learners in the settings of Selective Sampling (Cesa-Bianchi et al. 2006) and Label Efficient Prediction (Cesa-Bianchi et al. 2005 ) request labels randomly with a changing probability and achieve bounds on the expected number of mistakes and the expected number of label requests for a finite number of interactions. These algorithms cannot be used unmodified in the KWIK setting because, with high probability, KWIK algorithms must not make mistakes at any time; -In the MB-like Apple-Tasting setting (Helmbold et al. 2000) , the learner receives feedback asymmetrically only when it predicts a particular label (a positive example, say), which conflates the request for a sample with the prediction of a particular outcome. -Query-by-committee algorithms (Seung et al. 1992; Freund et al. 1997b ) determine the confidence level of their predictions for an example based on the degree of disagreements in the predictions of sub-algorithms in the committee. Similarly to selective sampling algorithms, query-by-committee algorithms were proposed for active learning and may not possess the same accuracy requirement as KWIK. -Finally, the Averaged Classifier by Freund et al. (2004) may return ⊥ if the averaged prediction for an example is close to the classification boundary. However, it is assumed that examples are i.i.d. and a non-⊥ prediction may not be accurate. (Shafer and Vovk 2008) is an online learning paradigm in which the learner has to predict a region, rather than a point prediction, for the present input based on previously observed input-output pairs. It is required that these prediction regions contain the correct output with high probability. It is straightforward to decide whether the output is known within sufficient accuracy based on the "size" of the region. For example, in regression problems, if the region is an interval of length smaller than , then any point prediction in this region will be -accurate with high probability. However, existing conformal prediction methods make statistical assumptions about inputs such as independence or exchangeability, and thus are rendered inapplicable in the KWIK setting. Another framework similar to KWIK is the regret framework as applied to the Associative Bandit Problem (Strehl et al. 2006c) : at every timestep t in this model, the learner receives input x t ∈ X , selects an action a t from a possibly infinite set A, and then receives a randomized payoff r t ∈ , whose expectation depends on x t and a t . The goal is to minimize the regret, defined as the difference between the largest total payoff by following the best action-selection rule π in some given rule set and the total payoff received by the learner. No-regret algorithms have been found for variants of associative bandit problems in the sense that their regrets are sublinear in the number of timesteps (e.g., Auer 2002). Consequently, the average per-timestep regret converges to 0 in the limit. However, these algorithms do not satisfy the KWIK requirements for exactly the same reason that MB algorithms are not KWIK: the learner does not know for certain when the last mistake is made, even if the overall probability of mistaken predictions is tiny. Mach Learn (2011) 82: 399-443  This section describes some hypothesis classes for which KWIK algorithms are available. It is not meant to be an exhaustive survey, but simply to provide a flavor for the properties of hypothesis classes KWIK algorithms can exploit. The complexity of many learning problems has been characterized by defining the dimensionality of hypothesis classes (Angluin 2004) . No such definition has been found for the KWIK model, so we resort to enumerating examples of learnable classes. We begin by describing the simplest and most general KWIK algorithms. X with a KWIK bound of |X |. This algorithm can be used when the input set X is finite and observations are noise free. To achieve this bound, the algorithm simply keeps a mappingĥ initialized toĥ(x) = ⊥ for all x ∈ X . When the environment chooses an input x, the algorithm reportsĥ(x). If h(x) = ⊥, the environment will provide a label y and the algorithm will assignĥ(x) := y. It will only report ⊥ once for each input, so the KWIK bound is |X |. The algorithm keeps track ofĤ, the version space, and initiallyĤ = H. Each time the environment provides input x ∈ X , the algorithm computesL = {h(x) | h ∈Ĥ}. That is, it builds the set of all outputs for x for all hypotheses that have not yet been ruled out. If |L| = 0, the version space has been exhausted and the target hypothesis is not in the hypothesis class (h * ∈ H). If |L| = 1, it means that all hypotheses left inĤ agree on the output for this input, and therefore the algorithm knows what the proper output must be. It returnsŷ ∈L. On the other hand, if |L| > 1, two hypotheses in the version space disagree. In this case, the algorithm returns ⊥ and receives the true label y. It then computes an updated version spacê Because |L| > 1, there must be some h ∈Ĥ such that h(x) = y. Therefore, the new version space must be smaller: |Ĥ | ≤ |Ĥ| − 1. Before the next input is received, the version space is updatedĤ :=Ĥ . If |Ĥ| = 1 at any point, |L| = 1, and the algorithm will no longer return ⊥. Therefore, |H| − 1 is the maximum number of ⊥s the algorithm can return. Example 1 You own a bar that is frequented by a group of n patrons P . There is one patron f ∈ P who is an instigator-whenever a group of patrons is in the bar G ⊆ P , if f ∈ G, a fight will break out. However, there is another patron p ∈ P , who is a peacemaker. If p is in the group, it will prevent a fight, even if f is present. Mach Learn (2011) 82: 399-443 407 You want to predict whether a fight will break out among a subset of patrons, initially without knowing the identities of f and p. The input set is X = 2 P and the output set is Y = {fight, no fight}. The memorization algorithm achieves a KWIK bound of 2 n for this problem, since it may have to see each possible subset of patrons. However, the enumeration algorithm can KWIK-learn this hypothesis class with a bound of n(n − 1) − 1 since there is one hypothesis for each possible assignment of a patron to f and p. Each time it reports ⊥, it is able to rule out at least one possible instigator-peacemaker combination. The previous two algorithms exploited the finiteness of the hypothesis class and input set. KWIK bounds can also be achieved when these sets are infinite. Problem 3 Define X = n , Y = , and The algorithm maintains a training set T of training examples, which is initialized to the empty set ∅ prior to learning. On the t th input )} be the current set of training examples. The algorithm first detects if x t is linearly independent of the previous inputs stored in T . This can be done efficiently by, say, Gaussian elimination (Golub and Van Loan 1989) . If x t is linearly independent, then the algorithm predicts ⊥, observes the output y t = f (x t ), and then expands the training set: T ← T ∪ {(x t , y t )}. Otherwise, there exist k real numbers, a 1 , a 2 , . . . , a k , such that In this case, we can accurately predict the value of f (x t ) using linear algebra: By operation of the algorithm, the inputs in T (that is, v 1 , v 2 , . . . , v k ) must be linearly independent at all times. Hence, T contains at most n training pairs, so the algorithm will predict ⊥ at most n times. Any case where the inputs contain n such linearly independent vectors shows this KWIK bound is tight. The deterministic linear regression algorithm above may be used by the distance learning below to learn the 2 -distance between two points. n , Y = , and Mach Learn (2011) 82: 399-443 where The distance learning algorithm can learn in this hypothesis class with a KWIK bound of n + 1. Although this problem can be solved using a geometric argument , it is easier to describe the solution via a reduction to deterministic linear regression. 3 We start with the squared 2 -distance of an input x to the unknown point c: The right-hand side may be viewed as a linear function,c Tx , wherex andc are the augmented input and weight vectors, respectively: Therefore, we may use deterministic linear regression to KWIK-learn the function, x − c 2 − x 2 , with a KWIK bound of n + 1. If we can make an accurate prediction for this function, we can easily compute the distance x − c . Up to this point, observations have been noise free. In this subsection, we consider a couple of noisy KWIK learning problems. We start with the simplest Bernoulli case and note that the same algorithm can actually be applied to KWIK-learn the expectation of a bounded, real-valued random variable. The coin learning algorithm can accurately predict the probability that a biased coin will come up heads given Bernoulli observations with a KWIK bound of We have a biased coin whose unknown probability of heads is p. In the notation of this paper, X is a singleton containing an arbitrarily chosen element (meaning that we have a single coin with a fixed but unknown head probability), Y = [0, 1], and Z = {0, 1} with 0 for tail and 1 for head. We want to learn an estimatep that is accurate (|p − p| ≤ ) with high probability (1 − δ). If we could observe p, then this problem would be trivial: Say ⊥ once, observe p, and letp = p. The KWIK bound is thus 1. Now, however, observations are noisy. Instead of observing p, we see either 1 (with probability p) or 0 (with probability 1 − p). Each time the algorithm says ⊥, it gets an independent trial that it can use to compute the empirical probability:p = 1 T T t=1 z t , where z t ∈ Z is the t th observation in T trials. The number of trials needed before we are 1 − δ certain our estimate is within -accuracy can be computed using a Hoeffding (1963) bound: 3 This approach was suggested by Robert Schapire. Mach Learn (2011) 82: 399-443 409 The coin-learning problem above can be regarded as a special case of the dice-learning problem. Here, the agent is to KWIK-learn a multinomial distribution over n elements, where each distribution is specified by n non-negative numbers that sum up to unity. The prediction error is defined as the total variance between the true distribution and the learner's prediction; given two discrete distributions, y andŷ, over the same discrete sample space, , their total variation is defined as half of their 1 distance: |y −ŷ| := 1 2 ω∈ |y(ω) −ŷ(ω)|. The dice learning algorithm can accurately predict a multinomial distribution over n elements within total variation given multinomial observations with a KWIK bound of The algorithm is almost identical to coin learning. It first draws T samples from the multinomial distribution and then uses the empirical distribution for prediction. To derive a KWIK bound for dice learning, we may use coin learning to KWIK-learn each probability in the multinomial distribution h = (h(ω 1 ), h(ω 2 ), . . . , h(ω n )) to ensure /n accuracy with probability at least 1 − δ/n. Then, an application of the union bound yields the following KWIK bound for dice learning which is asymptotically worse than the stated bound. However, a more careful analysis using the multiplicative form of Chernoff's bound can prove the stated KWIK bound. A proof is given by Kakade (2003) . The dice learning algorithm will serve as an important building block in many of our applications to reinforcement learning. The important case of noisy linear functions is studied in Sect. 5. This section extends the deterministic linear regression algorithm (Problem 3) to the noisy case where the observations are target outputs corrupted by additive, white noise. The algorithm we present here is based on previous work by Strehl and Littman (2008) , who first formulated and solved this problem. Recently, two related algorithms were developed. Walsh et al. (2009) considered a slightly different setting than the one defined in Sect. 3. Specifically, their algorithm can always see the label even if it makes a valid prediction, although a later refinement of this work (available as a technical report) performed the analysis under the same conditions as the algorithm above. The sample complexity results for this algorithm were on par with those reported here, but because it employed regularization, the computation and storage requirements were both polynomial in the number of dimensions, rather than growing with the number of samples as an naive implementation of the algorithm above would. In that light, this later work can be viewed as a practical version of the one presented here, but with slightly different mechanics. Cesa-Bianchi et al. (2009) studied selective sampling for binary classification with linear classifiers. Under a weaker assumption that the environment is an oblivious adversary 410 Mach Learn (2011) 82: 399-443 (namely, the sequence of inputs is fixed beforehand), their Parametric BBQ algorithm achieves a significantly better KWIK bound ofÕ(d/ 2 ), whereÕ(·) suppresses logarithmic factors. The KWIK bound we present in this section, however, remains valid even when the environment is adaptive, that is, when the environment has the ability to decide the next input based on previous interaction history with the learner. Furthermore, their bound has a logarithmic dependence on the total number of timesteps. In contrast, our KWIK bound here (as well as the one by Walsh et al. 2009) does not have this dependence-a property that is necessary for the KWIK algorithm's application to reinforcement learning in Sect. 7.2. In the noisy linear regression problem, certain regularity assumptions are necessary to make it feasible. Recall that for a vector x ∈ n , we denote its 2 norm by x . 1], and The deterministic case was described in Sect. 4.2 with a KWIK bound of n. Here, the algorithm must be cautious to average over the noisy samples to make predictions accurately. The algorithm uses the least-squares estimate of the weight vector for inputs with high certainty. Certainty is measured by two terms representing (1) the number and proximity of previous samples to the current input and (2) the appropriateness of the previous samples for making a least-squares estimate. When certainty is low for either measure, the algorithm reports ⊥ and observes a noisy sample of the linear function. Problem 7 Define Let X ∈ m×n denote an m × n matrix whose rows we interpret as transposed input vectors. We let X(i) denote the transpose of the ith row of X. Let z ∈ m denote an m-dimensional vector whose ith component, denoted z(i), is interpreted as the corresponding noisy observation. Since X T X is symmetric and positive semi-definite, it can be written as the following form of singular value decomposition (Golub and Van Loan 1989): where U = [u 1 , . . . , u n ] ∈ n×n , with u 1 , . . . , u n being a set of orthonormal singular vectors of X T X, and = diag(λ 1 , . . . , λ n ), with corresponding singular values For a fixed input x t (a new input provided to the algorithm at time t ), definē Mach Learn (2011) 82: 399-443 411 Our algorithm uses these quantities and is provided in pseudocode by Algorithm 1. The main result about this algorithm is the following theorem. Although the analysis of Algorithm 1 is somewhat complicated, the algorithm itself has a natural interpretation. Given a new input x t , the algorithm considers making a prediction of the output y t using the norm-constrained least-squares estimator (specifically,θ defined in line 6 of Algorithm 1). The norms of the vectorsq andū provide a quantitative measure of uncertainty about this estimate. When both norms are small, the estimate is trusted and a valid prediction is made. When either norm is large, the estimate is not trusted and the algorithm produces an output of ⊥. The quantitiesq andū provide a measure of uncertainty for the least-squares estimate (Auer 2002). Consider the case when all eigenvalues of X T X are greater than 1. In this case, note that Thus, x can be written as a linear combination, whose coefficients make upq, of the rows of X, which are previously experienced inputs. Intuitively, if the norm ofq is small, then there are many previous training samples (actually, combinations of inputs) "similar" to x, hence their noises cancel each other, and our leastsquares estimate is likely to be accurate for x. For the case of ill-conditioned X T X (when X T X has singular values close to 0), X(X T X) −1 x may be undefined or have a large norm. In this case, we must consider the directions corresponding to small singular values separately viaū: if ū is sufficiently small, this direction can be ignored without significantly affecting the prediction; otherwise, the algorithm predicts ⊥. Our analysis of Algorithm 1 hinges on two key lemmas that we now present. They together show that the cumulative squared error of a predictor can be used to bound its prediction error on a new input, a critical insight used to prove Theorem 1. The complete proofs are given in Appendix A. Let x t denote the input at timestep t . Algorithm 1 Noisy Linear Regression Computeq andū using Equations 2 and 3. if q ≤ α 1 and ū ≤ α 2 then 6: Chooseθ ∈ n that minimizes i (z(i) −θ T X(i)) 2 subject to θ ≤ 1. Predictŷ t =θ T x t . 8: Predictŷ t = ⊥. Receive observation z t . Append x T t as a new row to the matrix X. Append z t as a new element to the vector z. end if 14: end for 412 Mach Learn (2011) 82: 399-443 The first lemma analyzes the behavior of the squared error of predictions based on an incorrect estimateθ ( = θ ) versus the squared error obtained by using the true parameter vector θ . Specifically, we show that the squared error of the former is very likely to be larger than the latter when the predictions based onθ (of the formθ T x for input x) are highly inaccurate. The proof makes use of Hoeffding (1963)'s bound. n andθ ∈ n be two fixed parameter vectors satisfying θ ≤ 1 and θ ≤ 1. Suppose that (x 1 , z 1 ), . . . , (x m , z m ) is any sequence of samples satisfying with probability at least 1 − 2δ. The next lemma relates the error of an estimateθ T x for a fixed input x based on an incorrect estimateθ to the quantities q , ū , and Recall that when q and ū are both small, our algorithm becomes confident of the least-squares estimate. In precisely this case, the lemma shows that |(θ −θ) T x| is bounded by a quantity proportional to E (θ). This result justifies the condition used by Algorithm 1 to predict ⊥. n andθ ∈ n be two fixed parameter vectors satisfying θ ≤ 1 and θ ≤ 1. Suppose that (x 1 , z 1 )  We have that This section provides examples of how KWIK learners can be combined to provide learning guarantees for more complex hypothesis classes. Their applications in reinforcement learning are the topic of the next section. We first consider a variant of Problem 1 that combines learners across disjoint input sets.  Mach Learn (2011) 82: 399-443 413 The input partition algorithm runs the learning algorithm, denoted A i , for each subclass H i using parameters and δ/k. When it receives an input x ∈ X i , it queries A i and returns its responseŷ. Ifŷ = ⊥, an observation is obtained and input partition informs A i ofŷ to allow it to learn. Otherwise,ŷ is -accurate with high probability, as guaranteed by individual subalgorithms. The total number of ⊥s is the sum of the number of ⊥s returned by all subalgorithms A i . To achieve 1 − δ certainty, it insists on 1 − δ/k certainty from each of the subalgorithms. By a union bound, the overall failure probability must be less than the sum of the failure probabilities for the subalgorithms, which is at most δ. Example 2 Let X = Y = . Define H to be a set of piecewise linear functions: Using deterministic linear regression (Problem 3), we can KWIK-learn the class of linear functions over two input sets, X − = (−∞, 0) and X + = [0, ∞), each requiring a KWIK bound of 1. Note that {X − , X + } is a partition of the entire input set: X − ∪ X + = X and X − ∩ X + = ∅. We can use input partition to KWIK-learn H with a KWIK bound of 1 + 1 = 2. The two KWIK learners are called A − and A + , respectively. Assume the first input is x 1 = 2, which is in X + . The input partition algorithm queries A + with input x 1 . Since A + has no idea about y 1 , it returns ⊥. Hence, input partition reportsŷ 1 = ⊥, and y 1 = 4 is observed. Learner A + can now infer with certainty that p = y 1 /x 1 = 2, and we can now predict f (x) for all x ∈ X + . The next input is x 2 = 0.5 ∈ X + , which is again presented to A + , resulting inŷ 2 = px 2 = 1. The third input is x 3 = −1 ∈ X − . The algorithm queries A − with input x 3 and receives ⊥ since A − does not have enough information to predict y 3 . The algorithm then predicts ⊥ for the second time and sees y 3 = 3. Learner A − can now determine m = y 3 /x 3 = −3, and the target function is completely identified: A similar approach applies to the output set Y when it is a cross product of k sets: Since the accuracy requirement in Definition 1 depends on the output set as well as the interpretation of the discrepancy metric | · |, it is necessary to make certain assumptions to relate the discrepancy metric of Y to those of Y i . A natural choice, which we will use in Sect. 7, is to assume the existence of some α ∈ (0, 1] such that for any ∈ (0, 1) and any  The next algorithm generalizes the previous algorithm by combining both the input and output sets.  Here, each input consists of a vector of inputs from each of the sets X 1 , . . . , X k and outputs are vectors of outputs from Y 1 , . . . , Y k . Like Problem 9, each component of this vector can be learned independently via the corresponding algorithm. Each is learned to within an accuracy of α and confidence 1 − δ/k. Any time any component returns ⊥, the cross product algorithm returns ⊥. Since each ⊥ returned can be traced to one of the subalgorithms, the total is bounded as described above. By the union bound, total failure probability is no more than k × δ/k = δ. We note that Problem 9 is a degenerate case in which X i = X j for all i, j and each input vector contains the same element in its components. Example 3 You own a chain of k bars, each of which is frequented by a set of n patrons, P i , and once again each bar has an instigator f i ∈ P i and a peacemaker p i ∈ P i . The patron sets do not overlap. On any given night, with some subset of each P i at each bar, you need to predict whether, for each bar, there will be a fight. Notice that input partition cannot solve this problem because a prediction must be made for each bar, and output combination is similarly insufficient because there are k disjoint input sets. But using cross product with enumeration (Problem 2) for each bar achieves a KWIK bound of k(n(n − 1) − 1). We note that generally cross product can be wrapped around several different learners (e.g. enumeration for one sub-problem and memorization for another). The previous two algorithms concern combinations of input or output sets and apply to both deterministic and noisy observations. We next provide an intuitive algorithm for the deterministic case that combines hypothesis classes. ( , δ) where Problem 11 Let F ⊆ (X →Y The union algorithm is like a higher-level version of enumeration (Problem 2) and applies in the deterministic setting. It maintains a set of active algorithmsÂ, one for each hypothesis class:Â = {1, . . . , k}. Given an input x, the union algorithm queries each algorithm i ∈Â to obtain a predictionŷ i from each active algorithm. LetL = {ŷ i | i ∈Â}. Furthermore, a union bound implies that, with probability at least 1 − δ, all predictions of A i must be /2-accurate whenever h * ∈ H i . If ⊥ ∈L, the union algorithm reports ⊥ and obtains the correct output y. Any algorithm i for whichŷ = ⊥ is then sent the correct output y to allow it to learn. When ⊥ / ∈L, we consider two cases as follows. IfL is consistent, meaning that there existsỹ ∈ Y such that maxȳ ∈L |ȳ −ỹ| < /2, then we claimỹ is -accurate with high probability: by assumption, one of the predictions inL, If, on the other hand,L is not consistent, meaning that there is noỹ ∈ Y such that maxȳ ∈L |ȳ −ỹ| < /2, then union returns ⊥ and obtains the correct output y. Any algorithm that makes a prediction error greater than /2 is eliminated for future consideration. That is,Â Clearly, at least one algorithm will be eliminated because any y ∈ Y must differ from at least one element inL by at least /2. On each input for which the union algorithm reports ⊥, either one of the subalgorithms reported ⊥ (at most i B i ( /2, δ/k) times) or two algorithms disagreed and at least one was removed fromÂ (at most k − 1 times). The KWIK bound follows from these facts. That is, each function in H 1 maps x to its distance from some unknown point c. We can learn H 1 with a KWIK bound of 2 using a 1-dimensional version of distance learning. Next, define That is, H 2 is the set of lines. We can learn H 2 with a KWIK bound of 2 using deterministic linear regression. Finally, define H = H 1 ∪ H 2 , the union of these two classes. We can use union to KWIK-learn H. Assume the first input is x 1 = 2. The union algorithm queries the learners for H 1 and H 2 with x 1 as input and neither has any idea, so it returns ⊥ and receives the feedback y 1 = 2, which it passes to the subalgorithms. The next input is x 2 = 8. The learners for H 1 and H 2 still don't have enough information, so it returns ⊥ and sees y 2 = 4, which it passes to the subalgorithms. Next, x 3 = 1. Now, the learner for H 1 unambiguously computes c = 4, because that's the only interpretation consistent with the first two examples (|2 − 4| = 2, |8 − 4| = 4), so it returns |1 − 4| = 3. On the other hand, the learner for H 2 unambiguously computes m = 1/3 and b = 4/3, because that's the only interpretation consistent with the first two examples (2 × 1/3 + 4/3 = 2, 8 × 1/3 + 4/3 = 4), so it returns 1 × 1/3 + 4/3 = 5/3. Since the two subalgorithms disagree, the union algorithm returns ⊥ one last time and finds out that y 3 = 3. It makes all future predictions (accurately) using the algorithm for H 1 . Finally, we provide a powerful algorithm that generalizes the union algorithm to work with noisy observations as well. The basic idea is similar to the method for hypothesis testing of , who consider a PAC-style learning model for probabilistic concepts.  Mach Learn (2011) 82: 399-443 We first sketch the special case of k = 2 to explain the intuition of noisy union, and then extend the analysis to the general case. This algorithm is similar to the union algorithm (Problem 11), except that it has to deal with noisy observations. The algorithm proceeds by running the KWIK algorithms, denoted A 1 and A 2 , using parameters ( 0 , δ 0 ), as subalgorithms for each of the H i hypothesis classes, where 0 = /4 and δ 0 = δ/3. Given an input x t in trial t , it queries each algorithm i to obtain a predictionŷ ti . LetL t be the set of responses. If ⊥ ∈L t , the noisy union algorithm reports ⊥, obtains an observation z t ∈ Z, and sends it to subalgorithms i withŷ ti = ⊥ to allow them to learn. In the following, we focus on the remaining cases where ⊥ / ∈L t . If |ŷ t1 −ŷ t2 | ≤ 4 0 , then these two predictions are sufficiently consistent, with high probability the predictionp t = (ŷ t1 +ŷ t2 )/2 is -close to y t = Pr(z t = 1). This is the case because one of the predictions, sayŷ t1 , deviates from y t by at most 0 with probability at least 1 − δ/3, and hence If |ŷ t1 −ŷ t2 | > 4 0 , then the individual predictions are not sufficiently consistent for noisy union to make an -accurate prediction. Thus, it reports ⊥ and needs to know which subalgorithm provided an inaccurate response. But, since the observations are noisy in this problem, it cannot eliminate h i on the basis of a single observation. Instead, it maintains the total squared prediction error for every subalgorithm i: e i = t∈T (ŷ ti − z t ) 2 , where T = {t | |ŷ t1 −ŷ t2 | > 4 0 } is the set of trials in which the subalgorithms gave inconsistent predictions. Our last step is to show that e i is a robust measure for eliminating invalid predictors when |T | is sufficiently large. Applying the Hoeffding bound and some algebra, we find Setting the righthand side to be δ/3 and solving for |T |, we have Since each A i succeeds with probability 1 − δ/3, and the comparison of e 1 and e 2 also succeeds with probability 1 − δ/3, a union bound implies that the noisy union algorithm succeeds with probability at least 1 − δ. All ⊥s are either from a subalgorithm (at most i B i ( 0 , δ 0 )) or from the noisy union algorithm (O(1/ 2 ln(1/δ))). The general case where k > 2 can be reduced to the k = 2 case by pairing the k learners and running the noisy union algorithm described above on each pair. Here, each subalgorithm is run with parameters /8 and δ/(k + 1). The algorithm is formally described in Algorithm 2. Although there are pairs, a more careful analysis can reduce the dependence of the KWIK bound on k from quadratic to linearithmic, 4 leading to Theorem 2, whose proof is given in Appendix B. Note we have not attempted to optimize the constant factor in parameter m, but the resulting KWIK bound is the best possible up to a constant ). Mach Learn (2011)  Predict the midpoint of the set of predictions:ŷ t = (max i∈Rŷti + min i∈Rŷti )/2 for all i, j ∈ R such that i < j and |ŷ ti −ŷ tj | ≥ /2 do 19:  when the parameter m is set appropriately: This section identifies a number of KWIK-learnable environments for reinforcementlearning (RL), each of which results in a sample-efficient algorithm for the corresponding class of environments. We first introduce the basic notation, define the way we measure sample complexity in online RL, and then examines several prominent cases from the literature. (s, a), is the expected cumulative reward received by taking action a in state s and following π thereafter. To maximize the total rewards received from the environment, the agent desires an optimal policy π * whose value functions, denoted by V * (s) and Q * (s, a), respectively, satisfy the conditions: V * = max π V π and Q * = max π Q π . Given the full model of an MDP (i.e., the five-tuple M), a set of standard algorithms exists for finding the optimal value function as well as the optimal policy, including linear programming, value iteration, and policy iteration (Puterman 1994) . However, if the transition and/or reward functions are unknown, the decision maker has to gather information by interacting with the environment. In a general reinforcement-learning setting which we call online RL, the agent chooses actions in discrete timesteps t = 1, 2, 3, . . . . At every timestep t , the agent occupies a single state, denoted s t , and has to choose an action a t ∈ A according to some policy, and observes a sampled transition: the next state it occupies is drawn from the transition function, s t+1 ∼ T (· | s t , a t ), and the immediate reward it receives is r t = R(s t , a t ). It is straightforward to generalize our results to the case where rewards are stochastic. We call the tuple s t , a t , r t , s t+1 a transition, which can be used as a training example for learning the reward and transition functions of the MDP. The learning agent may update its policy upon observing this transition. Therefore, an online RL algorithm can be viewed as a nonstationary policy that maps the sequence of transitions it observes so far to an action-selection rule. In contrast to stationary policies, nonstationary policies choose actions not just based on the current state, but also on previously experienced states, actions, and rewards. In the rest of this section, we focus on a class of RL algorithms known as model-based approaches (see, e.g., Moore and Atkeson 1993). These algorithms essentially learn the transition and reward functions of the underlying MDP, based on observed transitions, and then 5 For MDPs with infinite (e.g., continuous) state or action spaces, certain measure-theoretic assumptions are needed to guarantee the quantities we use, such as value functions and the Bellman operator (defined in Appendix C), are well-defined. This is beyond the scope of our paper, and interested readers are referred to Bertsekas and Shreve (1978) for details. Such assumptions are made implicitly in the rest of our paper. Mach Learn (2011) 82: 399-443 419 use MDP solutions such as dynamic programming to compute an optimal policy of the approximate MDPM. It is known that (through the various simulation lemmas in the literature such as Kearns and Singh (2002) as well as Lemma 9 in Appendix C) if the transition and reward functions ofM are close to those of M, the optimal policy ofM will be near-optimal in M. In model-based RL algorithms, therefore, the main challenge in learning is often that of learning the true MDP's transition and reward functions. Building on Kakade (2003)'s definition of sample complexity of exploration, Strehl et al. (2006a) formalizes the notion of PAC-MDP that can be viewed as an RL analogue to the PAC framework for supervised learning. Here, an RL algorithm is viewed as a non-stationary policy that takes actions based on history (including previously visited states and received rewards) and the current state. The number of timesteps during which this non-stationary policy is not near-optimal in the whole execution is called the algorithm's sample complexity of exploration (Kakade 2003 ). An algorithm is called PAC-MDP if its sample complexity is polynomial in relevant quantities, including the parameters that define the description complexity of the MDP, with high probability. At the core of all existing model-based PAC-MDP algorithms such as Rmax (Brafman and Tennenholtz 2002; Kakade 2003) lies the idea of distinguishing between known statesstates where the transition distribution and rewards can be accurately inferred from observed transitions-and unknown states. An important observation is that, if a class of MDPs can be KWIK-learned, then there exists an Rmax-style algorithm that is PAC-MDP for this class of MDPs. Theorem 3 formalizes this observation. The proof (in Appendix C) is through construction of a PAC-MDP algorithm called KWIK-Rmax that generalizes Rmax from finite MDPs to arbitrary MDPs. The proof relies on a form of the simulation lemma (Lemma 9), which relates value function approximation error to model approximation error, and on a generic PAC-MDP theorem given by Strehl et al. (2006a). 6 Definition 2 Fix the state space S, action space A, and discount factor γ .  then the sample complexity of exploration of KWIK-Rmax is The algorithm KWIK-Rmax (Algorithm 3) relies on two KWIK algorithms, A T (using parameters T , δ T ) and A R (using parameters R , δ R ), for KWIK-learning the MDP's transition and reward functions, respectively, and maintains an estimate of the MDP called the empirical known state-action MDP (Strehl et al. 2006a ). The estimate distinguishes two types of state-actions: for state-actions where both A T and A R can make valid predictions, the predictions must be accurate with high probability (the accuracy requirement for KWIK algorithms) and thus their dynamics are known; for other state-actions, their transition and reward functions cannot be accurately estimated and thus they are unknown. By assigning the largest possible reward (which is 1) to all unknown state-actions and let them self-loop, the agent is encouraged to explore these state-actions unless the probability of reaching them is too small. When the probability of reaching unknown states is small, we can show near-optimality of the greedy policy. Since the number of visits to an unknown state-action is polynomial in relevant quantities (the sample complexity requirement for KWIK algorithms), the number of timesteps the algorithm does not behave near-optimally is also a Compute a near-optimal value function Q t ofM such that Learn (2011) 82: 399-443 421 polynomial. This intuition is originally from Rmax (Brafman and Tennenholtz 2002) and the sample-complexity proof of Kakade (2003) , and is also the basic idea of our PAC-MDP proof in Appendix C. A few caveats are in order regarding practical issues when implementing Algorithm 3: 1. The definitions ofT andR are conceptual rather than operational. For finite MDPs, one may representT by a matrix of size O(|S| 2 |A|) andR by a vector of size O(|S||A|). For structured MDPs, more compact representations are possible. For instance, MDPs for some linear dynamical systems can be represented by matrices of finite dimension (Sects. 7.5 and 7.6), and factored MDPs can be represented by a dynamic Bayes net (Sect. 7.7). 2. It is unnecessary to updateT andR and recompute Q t for every timestep t . The known state-action MDPM (and thus Q * M and Q t ) remains unchanged unless some unknown state-action becomes known. Therefore, one may updateM and Q t only when A T or A R obtain new samples in lines 13 or 16. 3. It is unnecessary to compute Q t for all (s, a). In fact, it suffices to guarantee that Q t is This kind of local planning often requires less computation than global planning. 4. Given the approximate MDPM and the current state s t , the algorithm computes a nearoptimal action for s t . This step can be done efficiently using dynamic programming for finite MDPs. In general, however, doing so is computationally expensive (Chow and Tsitsiklis 1989). Fortunately, recent advances in approximate local planning have made it possible for large-scale problems Kocsis and Szepesvári 2006) . After explaining why existing computational learning models, PAC and MB, are not adequate for sample-efficient reinforcement learning in Sect. 7.3, the remaining subsections consider various subclasses of MDPs and unify most existing PAC-MDP algorithms using the KWIK framework developed in previous sections. Section 7.4 considers finite MDPs without considering generalization across states, while Sects. 7.5-7.7 show how generalization can be combined with KWIK to make use of structural assumptions of corresponding MDP classes to obtain more efficient RL algorithms. Finally, Sect. 7.8 shows how we may obtain a PAC-MDP algorithm for factored-state MDPs with unknown factorization structures by streamlining four KWIK algorithms we have developed, resulting in a novel algorithm that is significantly better than the state-of-the-art result. In all these cases, we focus on learning the transition function and assume the reward function is known. The extension to KWIK-learning reward functions is straightforward. The results are summarized in Table 1 . To simplify exposition and focus on application of KWIK in MDP learning, we avoid direct analysis of how to KWIK-learn the transition functions in terms of the 1 distance in Sects. 7.5 and 7.6, as required by Theorem 3. However, the discrepancy functions we use in those cases are both polynomially equivalent to the 1 distance. More details are found in the original papers (Strehl and Littman 2008; Brunskill et al. 2009 ). Given the relation between KWIK and PAC-MDP RL in the previous subsection, a natural question is whether the existing computational learning models such as PAC and MB are sufficient for MDP learning in reinforcement learning. We show that in general they are not. The argument against PAC stems from its distributional assumption: PAC assumes independently, identically distributed samples, which is clearly not true in online RL except quite restricted cases. Instead, the agent's shifting policy determines the samples it sees. This policy-driven sampling of state-actions is most conveniently viewed in the adversarial setting, which is outside the scope of PAC, but within the realm of MB. MB algorithms, however, are not necessarily capable of on-demand labeling of stateactions as known or unknown, a pivotal requirement for existing PAC-MDP algorithms. For instance, consider an exponentially large MDP where each state corresponds to a configuration of n Boolean variables and rewards are determined by a single conjunction over the current variable configuration. More specifically, there are two actions a 1 , which flips the rightmost bit, and a 2 , which shifts the bits left. If the state's configuration satisfies the unknown conjunction, either action produces a reward of 1, otherwise the reward is −1. Assume, for the sake of argument, the transition function is known. One can learn about the reward function by visiting all 2 n states, but an MB algorithm that defaults to "false" (c.f., Sect. 3.2) can learn conjunctions with only n + 1 mistakes, so it is tempting to adopt an MB perspective in learning the rewards. But this will not translate directly to a PAC-MDP algorithm because there is no basis for guiding exploration. At any time, states that have actually been experienced as "false" (−1 reward) and those that have never been explored (unknown reward) cannot be distinguished. They are both simply labeled "false". Thus, the agent could end up revisiting ("exploring") the same "false" state over and over, expecting a different reward. One could start labeling the states that have been explored, but this is by definition a KWIK algorithm! In contrast to MB and PAC, KWIK embodies the conditions sufficient for the model learning component of a model-based PAC-MDP algorithm. The KWIK framework harbors no distributional assumptions, and explicitly designates the known and unknown regions of the state/action space. As we saw in Sect. 3.2, this limits the models that can be efficiently learned to a proper subset of those that can be learned by MB, but we will show in the remaining subsections that this set still covers a large number of natural and interesting domain types from the reinforcement-learning literature. | s, a) . As the reinforcement-learning agent moves around in the state space, it observes state-action-next-state transitions and must predict the probabilities for transitions it has not yet observed. In the model-based setting, an algorithm learns a mapping from the size nm input set of state-action combinations to multinomial distributions over the next states via multinomial observations. Thus, the problem can be solved via input partition over a set of individual probabilities learned via dice learning. The resulting KWIK bound is This approach is precisely what is found in most sample-efficient RL algorithms in the literature (Kearns and Singh 2002; Brafman and Tennenholtz 2002; Kakade 2003; Strehl et al. 2006a ). More recently, Szita and Szepesvári (2010) propose a variant of Rmax and a refined analysis that results in a linearithmic dependence on n, matching the best previous bound (c.f., Sect. 7.9). We note that a similar idea can be applied to MDPs with infinite state and action spaces, provided that the MDPs satisfy the local modeling assumption . Intuitively, the dependence on sampling each state-action m times in the finite case is replaced by a requirement of gathering some m samples for each action in each partition of the space induced by the local modeling assumption. The KWIK bound for learning this type of MDPs is in general dependent on the smallest number of partitions (a.k.a. the covering number), rather than |S|. In many robotics and control applications, the systems being manipulated possess infinite state spaces and action spaces, but their dynamics are governed by a system of linear equations (see, e.g., Sontag 1998). Our model formulation is based on Strehl and Littman (2008) , and is slightly different from Abbeel and Ng (2005) . Here, S ⊆ n S and A ⊆ n A are the state and action spaces, respectively. The transition function T is a multivariate normal distribution: where φ : n S +n A → n is a basis function satisfying φ(·, ·) ≤ 1, F ∈ n S ×n is a matrix, σ 2 is some positive number, and I ∈ n S ×n S is the identity matrix. We assume φ and σ 2 are given, but F is unknown. For such linearly parameterized transition functions, the expectation of each component of the next state is linear in the feature of the current state-action, and the coefficients correspond to the numbers in the corresponding rows in F . If we define the discrepancy metric in n S as the 2 norm, then the transition function of the class of linearly parameterized MDPs can be KWIK-learned via output combination over the n S state components using α = 1/ √ n S , each of which can be KWIK-learned by noisy linear regression.  where μ τ (s)a ∈ n and τ (s)a ∈ n×n are the mean and covariance matrix of the normal distribution for the type-action pair (τ (s), a). In other words, the offset of states is normally distributed. We assume the number of actions, denoted m = |A|, and the number of types, denoted n τ = |{τ (s) | s ∈ S}|, are both finite. An example domain where such dynamics may arise is robot navigation across varying terrain. The distribution of the offset of the robot's position after taking an action (such as turn-left or go-forward) depends on the this action as well as the type of the terrain (such as sand, wood, or ice, etc.). In many real-world applications, the number of types is often small although the number of states can be astronomically large or even infinite. Typed offset dynamics, therefore, provide a compact way to represent the MDP. More motivations are found in Brunskill et al. (2009) . For each type-action (τ, a), the components in μ τ a and τ a can be interpreted as means of observations. For instance, assume that we have acquired a sample transition, (s, a, r, s ), then by definition for all i = 1, 2, . . . , n. Therefore, we may decompose the problem of KWIK-learning the offset means using input partition over all type-actions. For each (τ, a) pair, learning μ τ a is turned into one of KWIK-learning the mean of n random variables via output combination using α = 1, each of which can be solved by coin learning. 7 A similar reduction can be applied to KWIK-learn the covariance matrix τ a . To ensure the total variance between the true Gaussian distribution, N (μ τ a , τ a ), and the estimated distribu- tion, N (μ τ,a ,ˆ τ,a ) , is at most , the KWIK bound is  Without loss of generality, assume N = |S i | for all i and thus |S| = N n . The transition function is factored into the product of n transition functions, one for each state variable: In other words, the values of all the next-state variables are independent of each other, conditioned on the current state-action (s, a). Note that one can also define a DBN with "synchronous" edges, denoting a dependency between factor values at the same timestep. For simplicity, we do not consider such dependencies in our analysis, but the results are easily extended to this case by (at most) doubling the number of factors being considered as possible parents (though not the actual number of parents for any given node). Furthermore, we assume that the distribution Using the quantities defined above, the transition function can be rewritten as An advantage of this succinct representation is that, instead of representing the complete conditional probability table, T i (· | s, a), which has N n m entries, we only need to use the smaller T i (· | P(i), a), which has at most N D m entries. If D n, we are able to achieve an exponentially more compact representation. This kind of transition functions can be represented as dynamic Bayesian networks or DBNs (Dean and Kanazawa 1989). Here, we consider the case where the structure (P(i)) is known a priori and show how to relax this assumption in Sect. 7.8. The reward function can be represented in a similar way as the sum of local reward functions. We assume, for simplicity, that R(s, a) is known and focus on KWIK-learning the transition functions. Our algorithm and insights still apply when the reward function is unknown. ) , where D, as before, is the maximum in-degree of the true DBN. We can construct a conceptually simpler algorithm for this problem using components introduced throughout this paper. As a whole, the algorithm can be viewed as a four-level KWIK algorithm with a cross product at the top to decompose the transitions for the separate components of the factored-state representation. Each of these n individual factor transitions is learned using a separate copy of the noisy union algorithm. Within each of these, a union is performed over the Note that our noisy union component is conceptually simpler, significantly more efficient (k ln k vs. k 2 ln k dependence on k = n D ), and more generally applicable than the similar procedure employed by Strehl et al. (2007) . Thus, our improvement is exponential in D and polynomial in n. Preliminary studies show that the new algorithm works much better in practice ). The previous subsections discuss how to create model-based PAC-MDP RL algorithms with help of KWIK algorithms for various MDP subclasses. While model-based algorithms often have better sample complexity in practice, they usually maintain an implicit model of the unknown MDP and have to repeatedly solve this approximate MDP (such as in KWIKRmax) to obtain a value function or policy for taking actions. 9 Despite recent advances 8 Here, this value of α suffices to guarantee that the combined transition distribution differs from the true transition distribution by in terms of 1 -distance; see Li (2009) for a proof. 9 For finite MDPs, it is possible to replace exact planning by incremental planning (Strehl et al. 2006a) , which is much more efficient. Mach Learn (2011) 82: 399-443 427 in approximate planning in MDPs (see, e.g., Kocsis and Szepesvári 2006), solving MDPs remains challenging in general. In contrast, model-free algorithms directly learn optimal value functions, from which a greedy policy can be easily computed. These algorithms are therefore much more efficient in terms of both time and space. The first model-free PAC-MDP algorithm for finite MDPs, known as delayed Q-learning (Strehl et al. 2006b (Strehl et al. , 2009 , is a variant of Q-learning that carefully maintains an optimistic value function and takes greedy actions in all timesteps. The algorithm requires only (nm) space complexity and O(ln m) per-step time complexity to achieve a sample complexity ofÕ(nm/ 4 (1 − γ ) 8 ), where n and m are the numbers of states and actions. Recently, it was shown that the dependence on n is optimal (Li 2009; Strehl et al. 2009 ). In contrast, the best existing computational complexity is O(n ln m) (Strehl et al. 2006a) . Despite the nice computational advantages of model-free algorithms, these algorithms are unfortunately harder to analyze. In a recent work by Li and Littman (2010), a finitehorizon reinforcement learning problem is reduced to a series of KWIK regression problems so that we can obtain a PAC-MDP model-free RL algorithm as long as the individual KWIK regression problems are solvable. However, it remains unclear how to devise a KWIK-based model-free RL algorithm in discounted problems without first converting it into a finitehorizon one. We described the KWIK ("knows what it knows") model of supervised learning, which identifies and generalizes a key model learning component common to a class of algorithms for efficient exploration. We provided algorithms for a set of basic hypothesis classes given deterministic and noisy observations as well as methods for composing hypothesis classes to create more complex algorithms. One example algorithm consisted of a four-level decomposition of an existing learning algorithm from the reinforcement-learning literature. By providing a set of example algorithms and composition rules, we hope to encourage the use of KWIK algorithms as a component in machine-learning applications as well as spur the development of novel algorithms. Such a direction has seen promising results. Brunskill et al. (2009) successfully applied the algorithm in Sect. 7.6 to a robot navigation problem. More recently, an associative reinforcement learning algorithm motivated by the KWIK algorithm of Walsh et al. (2009) has showed encouraging results in a challenging online news article recommendation problem on Yahoo! Frontpage . The study in the present paper raises several important theoretical directions. We list seven of them to conclude the paper. First, we would like to extend the KWIK framework to the "unrealizable" case by removing the assumption that the hypothesis class H contains the true hypothesis h * . This is sometimes called agnostic learning . We are able to provide a general-purpose KWIK algorithm when H is finite, resulting in a KWIK bound of O(|H|), 10 but it remains open how to handle unrealizable target functions with infinite-size hypothesis classes. Second, it is not clear how to characterize the dimension, dim(H), of a hypothesis class H in a way that can be used to derive KWIK bounds. For finite hypothesis classes, the 10 This bound can be achieved by a variation of enumeration. In this variant,Ĥ is the set of hypotheses that have been within -accuracy of the observed outputs, and the algorithm returns ⊥ if the range ofL is larger than 2 and otherwise it returns the midpoint of this set. Mach Learn (2011) 82: 399-443 cardinality of H is a reasonable choice, as is used in enumeration, but a more general definition is needed for infinite hypothesis classes. Similar efforts in the concept-learning literature (Angluin 2004) may provide useful insights for this problem. Third, it is important to find a general scheme for taking a KWIK algorithm for a deterministic class and updating it to work in the presence of noise. In the n-dimensional linear functions learning problem, we have seen that the KWIK bound grows from O(n) toÕ(n 3 ) by the algorithms of Strehl and Littman (2008) and Walsh et al. (2009) . In general, we expect the KWIK bound to increase significantly when noise is present unless the environment is oblivious (Cesa-Bianchi et al. 2009 ). Fourth, we would like to explore the relationship between KWIK and other online learning models. For instance, the selective sampling and label efficient prediction models share some similarity with KWIK and we might be able to modify algorithms in these frameworks to satisfy the KWIK criteria. Fifth, this paper only considers linear approximation architectures. It is possible that nonlinear architectures may be preferred in some cases given their greater representational power. A common approach to introducing nonlinearity in practice is to use a function that is linear in nonlinear features, but a direct analysis of nonlinear architectures in KWIK could be useful. Finally, it is of theoretical as well as practical interest to utilize prior information in KWIK. Prior information may be, for instance, a prior distribution of h * ∈ H. Ideally, a KWIK algorithm that makes use of such prior information should still satisfy the requirements in Definition 1, but may enjoy a significantly smaller KWIK bound by leveraging an informative prior. Acknowledgements This material is based in part upon work supported by the National Science Foundation under Grant No. NSF IIS-0325281 and a contract from DARPA IPTO. We thank Roni Khardon and the anonymous reviewers for valuable comments that have greatly improved an earlier draft of this paper. We also thank István Szita for many helpful discussions, and Mark Kroon for pointing out a mistake in our original presentation of the algorithm in Sect. 7.8.
KWIK 'Knows What It Knows' frameworks REF allow for active exploration which is beneficial in reinforcement learning problems.
Knows what it knows: a framework for self-aware learning
Machine Learning
Machine Learning
Computer Science