(11th-January-2021)
In addition to its role in defining idealized intelligent agents, Kolmogorov complexity can also be used to define measures of intelligence (Hernández-Orallo 2000). Legg's and Hutter's (2006) formal measure of intelligence is closely related to universal AI. This measure is defined in terms of the expected values of utility functions that the agent can achieve. In order not to favor agents that simply have high utility function values, the measure is only defined for agents whose utility function values are rewards from the environment as u(h) = r|h|. The measure is different from AIXI in that it assumes stochastic environments. Note that it is not sufficient to use a non-deterministic reference UTM, because non-deterministic TMs do not specify probabilities of their possible next states. Rather, the programs for the reference UTM must compute probabilities for observations as functions of agent actions.
Given an agent π and an environment μ, an interaction between π and μ will produce a sequence of rewards ri for i = 0, 1, 2, … (either infinite or up to some final time step). The value of agent π in environment μ is defined by the expected value of the sum of future, discounted rewards:
(3.2) Vμπ = E(∑i≥0 γiri).
Note that Legg and Hutter assumed that discounts are built into rewards and so did not explicitly include γi in equation (3.2), but I include it to make it clear that (3.2) converges (we also assume that 0 ≤ ri ≤ 1). This expected value is the average value of the sum of discounted rewards over many interactions between π and a stochastic environment μ. The intelligence of agent π is defined by a weighted sum of its values over a set E of computable environments. Environments are computed by programs, finite prefix-free binary strings, on some reference UTM U. The weight for μ ∈ E is defined in terms of its Kolmogorov complexity:
K(μ) = min { |p| : U(p) computes μ }
where |p| denotes the length of program p. The intelligence of agent π is then defined as:
(3.3) Vπ = ∑μ∈E 2-K(μ) Vμπ.
Reference UTMs pose subtle problems. I showed (Hibbard 2009) that given an arbitrary environment μ ∈ E and ε > 0, there exists a reference UTM Uμ such that for all agents π and for Vπ computed according to Uμ,
Vμπ / 2 ≤ Vπ <Vμπ / 2 + ε.
That is, the intelligence of any agent can be determined, within an arbitrarily small epsilon, by its value with respect to any single environment we choose, simply by picking the appropriate reference UTM. As Legg and Hutter suggested, it may be useful to apply some criterion to reference UTMs, such as picking the UTM with the smallest number of states. It is worth noting that if AIXI and an intelligence measure share the same reference UTM, then AIXI has the maximum possible intelligence by that measure.
Comments