## 3 History and State-of-the-Art
Meanwhile, the (non)existence of universal priors for several generalized computability concepts [66, 86, 87] has been classified, rapid convergence of \(M\) to the unknown true environmental distribution \(\mu\)[88] and tight error [89] and loss bounds for arbitrary bounded loss functions and finite alphabet [90, 91] have been proven, and (Pareto) optimality of \(M\)[18, 86] has been shown, exemplified on games of chance and compared to predictions with expert advice [18, 92]. The bounds have been further improved by introducting a version of Kolmogorov complexity that is monotone in the condition [93, 94]. Similar but necessarily weaker non-asymptotic bounds for universal deterministic/one-part MDL [95, 96] and discrete two-part MDL [97, 98, 99, 100] have also been proven. Quite unexpectedly [101]\(M\) does _not_ converge on all Martin-Lof random sequences [102], but there is a sophisticated remedy [103]. All together this shows that [PERSON]'s induction scheme represents a universal (formal, but incomputable) solution to all _passive_ prediction problems. The most recent studies [104] suggest that this theory could solve the induction problem at whole, or at least constitute a significant progress in this fundamental problem [31]. **Sequential decision theory. ** Sequential decision theory provides a framework for finding optimal reward-maximizing strategies in _reactive_ environments (e.g. chess playing as opposed to weather forecasting), assuming the environmental probability distribution \(\mu\) is known. The Bellman equations [30] are at the heart of sequential decision theory [25, 58, 105]. The book [20] summarizes open problems and progress in infinite horizon problems. Sequential decision theory can deal with actions and observations depending on arbitrary past events. This general setup has been called AI\(\mu\) model in [19, 27]. Optimality of AI\(\mu\) is obvious by construction. This model reduces in special cases to a range of known models. **Reinforcement learning. ** If the true environmental probability distribution \(\mu\) or the reward function are unknown, they need to be learned [59]. This dramatically complicates the problem due to the exploration\(\hookrightarrow\)exploitation dilemma [27, 106, 107, 108]. In order to attack this intrinsically difficult problem, control theorists typically confine themselves to linear systems with quadratic loss function, relevant in the control of (simple) machines, but irrelevant for AI. There are notable exceptions to this confinement, e.g. the book [109] on stochastic adaptive control and [110, 111], and an increasing number of more recent work. Reinforcement learning (RL) (sometimes associated with temporal difference learning or neural nets) is the instantiation of stochastic adaptive control theory [109] in the machine learning community. Current research on RL is vast; the most important conferences are ICML, COLT, ECML, ALT, and NIPS; the most important journals are JMLR and MLJ. Some highlights and surveys are [112, 113, 114, 115, 116, 117, 118, 119, 120] and [131, 132, 133, 20, 59] respectively. RL has been applied to a variety of real-world problems, occasionally with stunning success: Backgammon and Checkers [59, Chp.11], helicopter control [134], and others. Nevertheless, existing learning algorithms are very limited (typically to Markov domains), and non-optimal -- from the very outset they are approximate or asymptotic only. Indeed, AIXI is currently the only general and rigorous mathematical formulation of the addressed problems. **The universal algorithmic agent AIXI. ** Reinforcement learning algorithms [59, 131, 135] are usually used in the case of unknown \(\mu\). They can succeed if the state space is either small or has effectively been made small by generalization techniques. The algorithms work only in restricted, (e.g. Markov) domains, have problems with optimally trading off exploration versus exploitation, have non-optimal learning rate, are prone to diverge, or are otherwise ad hoc.