We consider a special case of reinforcement learning where the environment can be described by a linear system.The states of the environment and the actions the agent can perform are represented by real vectors and the system dynamic is given by a linear equation with a stochastic component.The problem is equivalent to the so-called linear quadratic regulator problem studied in the optimal and adaptive control literature.We propose a learning algorithm for that problem and analyze it in a PAC learning framework.Unlike the algorithms in the adaptive control literature, our algorithm actively explores the environment to learn an accurate model of the system faster.We show that the control law produced by our algorithm has, with high probability, a value that is close to that of an optimal policy relative to the magnitude of the initial state of the system.The time taken by the algorithm is polynomial in the dimension n of the state-space and in the dimension T of the action-space when the ratio n/r is a constant.Permission to make digilnl/hnrd copirs ofall OI-pa11 oFthis rna~~rial I~I personal or clmroow we is grnnled withoul fee provided fhnt ~hr copies are nd made or dis\rilwted for proiii or commercinl adv:~n~;rge.11,~ copyright notice.the We oTllw puhlic:~~iw and iIs dnu appe:w.;wd notice is given lhnl copyrighl is hy prmissio~~ ol'thc ,\C'bl.lw '1'0 cqq otlwwisc.to republish, IO post on serum or to raiixtrlhul~ IO tlhls, rcqulra \pccitic pernlissioll mid/or fee C'OLT 97 Nashville, Tcnuesee.USA

In this paper we propose a new formal model for studying reinforcement learning, based on Valiant's PAC framework. In our model the learner does not have direct access to every state of the environment. Instead, every sequence of experiments starts in a fixed initial state and the learner is provided with a "reset" operation that interrupts the current sequence of experiments and starts a new one (from the initial state). We do not require the agent to learn the optimal policy but only a good approximation of it with high probability. More precisely, we require the learner to produce a policy whose expected value from the initial state is "-close to that of the optimal policy, with probability no less than 1 \\Gamma ffi . For this model, we describe an algorithm that produces such an (",ffi)-optimal policy, for any environment, in time polynomial in N , K, 1=", 1=ffi, 1=(1 \\Gamma fi) and r max , where N is the number of states of the environment, K is the maximum number of actions in a...