by just plugging solomonov into um into
the sequential decision framework um
sounds like an optimal decision maker in
arbitrary unknown worlds and if you sort
of if you par the sentence this feels
like AI whole conversation by Marvin
vinsky was and I'm paraphrasing I don't
know exactly but pretty much um Solomon
of's theory is a beautiful theory about
prediction
everyone should know everything about
this theur and spend the rest of their
lives working on
it welcome everyone to the cartisian
cafe I am your host Tim win today we're
very lucky to have Marcus hutter here
with us Marcus is an artificial
intelligence researcher who is a both a
senior researcher at Google Deep Mind
and an honorary professor in the
research School of computer science at
Australian National University he is
responsible for the development of the
theory of universal artificial
intelligence for which he has written
two books one back in 2005 and one
coming right off the press as we speak
Marcus is also the creator of the hutter
prize for which you can win a sizable
Fortune for achieving State of-the-art
lossless compression of Wikipedia text
welcome Marcus how are you doing
today hi Tim I'm fine
thanks yeah great uh I'm glad I'm
finally able to interview one of my
colleagues at Google deep mine of course
it goes without saying that everything
we discuss is reflective of our own
thoughts and opinions and not those of
of our employers um that being said uh
before we dive into the details of what
will uh be a very fascinating topic um
why don't we talk a little bit about
your background uh you apparently
started out in life as a physicist and
then transitioned to computer science
and AI uh maybe can you say a few words
about uh why and how that
happened um yes it's actually a little
bit more complicated uh at some point in
my life I realized I was born already as
a beian but I mean we don't have to
really dig into this I always had
discussions with other people and before
I knew about frequentist invasions and
uh and then later I realized okay most
of people are B frequentists because I
mean they learned that at University and
I'm beian so I always say no I'm born a
beian but no my my interests from a very
young age were uh twofold one was
understanding the
universe which naturally leads to to you
know want to study Physics um and the
other one is creating AI um so I toggled
back and forth between so I did a I mean
the German equivalent of a bachelor in
computer science then a bachelor in
physics then a masters in computer
science then a PhD in theoretical
particle physics then I had a four and a
half years stint in the industry uh but
then I really wanted to return to do
fundamental research and sort of then
since the year 2000 uh I finally settled
uh to working on
AI okay
um all right great um maybe one more
question uh what's the backstory behind
your hutter priz why did you create it
why do you care about it and how did you
secure the funds for it oh okay so
um the reason
is essentially one reason yeah but sort
of it's multiple facets um is we will uh
discuss in this podcast
um there is a close relation between
being able to compress data and being
able to predict data actually the
prediction compression relation is is in
a sense perfect right there is no no
difference between prediction and um and
compression and being able to predict
well is at least I would say half the
rent um for um a general intelligent
agent um so um if you want to behave
well um in an uncertain world uh you
need to make predictions and then you
know make plans and decisions
accordingly um and if your predictions
are bad then you know even if your
decision algorithm is good your your
actions will be bad so and so this
connection um is pretty obvious for you
know a set of people who you know work
on compression stochastic compression is
peculiar and it's now
meanwhile um since we have the large
language models and they're trained on
log loss so so this Duality between
Corporation and prediction now is
becoming mainstream but when I started
the compression price that was not so
well known and I wanted to to advertise
that um but apart from advertising I
also want to solve the AI problem so and
since prediction is one half of it we
need better predictors which means
better compressors so I thought I want
to encourage people to come up with
better compressors because that is
closely related to um then prediction n
Ai and uh as we will discuss briefly
probably um these llms are essentially
you know the models the better they
compress the better they perform on on
Downstream tasks and with the secur of
the funds yeah I made a big gamble I
mean initially it was only um nominally
50,000 Euro uh but you don't get the
50,000 in one go you only if you beat
the current state of the art by x% you
get x% of the price and my reasoning was
I mean either progress is slow which I
expected and then I can afford to pay it
out um or uh progress is sudden then
this is such a major event that I'm
willing sort of you know to to to scrape
somehow the funds um and I mean
meanwhile it's 500,000 EUR nominally um
but usually the improvements are you
know couple perent you know every couple
of years so I only have to P py out you
know smaller amounts um and yeah I mean
if suddenly somebody compresses to half
size uh um then um yeah I have to take
another mortgage on my
house okay um but I will I will
definitely honor um my commitment so
don't don't worry about that I'm so all
right I I I hope uh you'll get a flood
of participants after our uh
conversation um thank you Marcus um
before we dive into the details why
don't we get an overview from you about
the theory of universal artificial
intelligence uh you're responsible for
its creation um can you say a few words
at a high level what it is and why
people should care about it ah sure yeah
so um okay let me go back a little bit
um so
um as I said I couldn't decide between
physics and AI um physics um had
beautiful math and elegant theories and
so on while on the other hand I believe
that AI AGI now um has um more impact um
more practical impact uh but at the time
at least at the '90s when I studied it
um AI wasn't really I mean the field
wasn't really too attractive to me sort
of there was good oldfashioned AI with
logical reasoning expert system which
was sort of reasonably formal but I
never believed that this is the way to
uh uh to to through AGI um and then
there were of course neural networks but
um I didn't like the neural networks uh
too much um and I mean they work to some
extent but also not very well and um
anyway and I didn't have any good ideas
myself yeah so um so I left the field
worked for four and a half years in a
startup but after a while after a couple
of years I couldn't stop thinking again
about Ai
and finally more or less you know in an
instant I
realized what has to be done and what
was missing um and uh to keep it short
um many
fields start out in an informal way and
then they get more and more formal uh
which helps sort of this with the
technical and the scientific development
think about physics you the energy was a
mysterious concept and and the kinds of
things that now it's you rigorously
formal and but if you look at AI nobody
has really formally defined what
intelligence is but AI is about
artificial intelligence how can we work
about AI if we don't know what it is I
mean you know you can do it but I
thought it will be extremely useful to
know what is actually the ultimate goal
and I mean I knew for instance if you
play chess and we play Mini Max to the
end of the game that is a theoretical
optimal thing to do right so for for
perfectly wellp specified environments
um uh we know how to do the sequential
decision optimal way but um the world is
unknown and uncertain and we have to do
predictions and I wasn't aware at that
time neither about Kor of complexity nor
solom induction but then I realized um
generalization um via Kor complex in
solono which is sort of rediscovered you
know but way to decades too late um um
is the way to go and um
so what
I discovered is or RIS discovered is
that you can make predictions of
arbitrary time serious whether it is
Market data uh weather forecasting or
you know number sequences 1 2 3 4 five
or or any data you can do that in a in a
certain sense in an optimal way without
knowing the underlying structure of the
problem
using what is has been known even at the
time you know as Sol of induction using
color of complexity but that is only
prediction right and agents also act but
I knew sequence of decision solves the
action problem if you know the
environment and I just I mean in Hite I
put these things two together and
arrived at a model which does
optimal decisions in arbitrary unknown
worlds and if you think about this
sentence right this is what AGI is or
should be about and that's what I call
universally I um wrote down the
mathematics and you know the last 25
years uh proved a lot of theorems about
it and we also approximated to some
extent and implemented it and so there's
now even you know nice connections to
actually large language models and we
probably little bit talk about this um
if there's somebody here uh listening um
who primarily or only cares about large
language model so they will be covered
okay great all right great well uh yeah
that that's a lot to unpack so I think
probably the best way uh forward is
let's just start writing a technical
outline because I think once we start
getting into the details U more of this
will become uh clear and and uh yeah so
let's let's now go to the whiteboard and
I'll uh start with uh writing a list of
topics that I think we'll we'll be
covering and and and following and of
course we'll adjust along the way um
so the first kind of um uh phenomenon
will be discussing is what's called
Universal prediction which is what you
alluded to before and
uh you know without loss of generality I
what is what is the problem of universal
prediction basically we're given um a
sequence of zeros and
ones in general it could be an arbitrary
alphabet but binary is is is sufficient
to to to illustrate the point uh we want
to predict
probability of
next
digit right so that's that's the
prediction problem and it's Universal
and that we uh a priori there could be
any probability distribution uh
governing the sequence of zeros and ones
and our job is to sort of discover that
so to speak right and so this is the
universal prediction problem if I see a
stream of binary digits um can I use
that uh use that sequence of
observations to guide my prediction for
the next digit that I see right and um
the way we're going to kind of go about
uh explaining how to solve this problem
will be through a few steps um the first
thing we could do is start with the
warm-up which is to explain uh lass's
rule of
succession so this is one of these I
guess you can think of it as a simple uh
guideline of how to uh make the next
prediction given the observations but of
course there's a mathematical basis for
this and we'll go into that um and from
that warmup which I think will be a very
nice illustrative example to get people
familiar with the the problem if they
haven't seen it before um the kind of
the right frame work or the more General
framework for this is is beian sequence
prediction so sort of bean reasoning uh
underlies all of this and I guess maybe
that's not a surprise given you said
that you were born aan but of course you
know you start with the prior you make
some observations you update your
beliefs and then and just keep keep
iterating on that and we'll see how that
also um uh how lass's rule is a
instantiation of that um and sort of
that sets the stage for talking about
kagor of complexity
called magor of
complexity which uh philosophically when
we combine it with with beian reasoning
is a form of aams Razer as we'll see
right because because uh well uh aam
Riser is about you know keeping your
hypothesis as simple as possible and
kagor of complexity is a way of
measuring complexity and so we'll see
how those two things are related and and
and and tie that into beian resoning and
you already mentioned Sol Solomon of
induction so that will sort of be the
highlight of this section which is a way
of um
combining Kor of complexity uh with
beian sequence
prediction and in some sense this this
basically gives us a way of solving the
universal prediction problem right
that's that's what sort of Solomon of
induction does um so that's so this is
basically an over a very rapid overview
of the first part Universal prediction
and then sort of uh I add two things can
I add two things of course sure sure so
so here I would like to um mention a few
special special model classes which are
bigger than just predicting sort of IID
sequences but small enough so that you
can do that efficiently um you know the
names will come later and then after the
probably after it's um uh discuss loss
functions sure of course uh because it
somewhat ties into the next section
where we then deal with value functions
and loss is sort of more or less the
same as well sure sure sure right um
yeah that makes a lot of sense um of
course we want to get to Universal AI so
how do we get to there so that that
brings in the second section which is
we'll talk about
Universal uh agents and by agent that
basically means we're going to combine
prediction from the previous section
with planning right because agents act
and so if uh if you have a model of your
environment and you want to say optimize
your reward then that gives you a way of
planning right and and what we'll find
is that when we kind of combine uh the
ideas from uh the UN Universal
prediction side with
action and and and try to get something
that's optimal we get a
universal optimal agent which uh has
this uh well nice acronym ay artificial
intelligence cross induction right um
maybe just just to clarify bit when when
we talk about why we keep using the word
Universal Universal because we we don't
care what the um Environ or how do I say
the the environment can be arbitrary
just like the uh generative uh
distribution for our sequence of zeros
and ones in section one is also
arbitrary and so we want uh an OP a
solution that works for you know
arbitrary or general uh situations right
so that's this that I have to first
introduce agents in known environment Ah
that's
right
environment okay okay great and then uh
after we discuss those two well we'll
we'll just see what what we have time
for in terms of uh extra material right
so there's a lot we can cover your your
books have lots of material but just to
list a few that we might depending on
how much time we have uh we can talk
about say computable
approximations to all of this because uh
for those who know uh Kor of complexity
is is not a computable function in the
turg machine theoretic sense so of
course um uh this is nice Theory but if
you don't have something that's
computable maybe it might be limited and
so you want to come up with computable
approximations so that's something we uh
may want to discuss there's also maybe
multi-agent settings where there's more
than one actor right and um and maybe
def multi-agent we should definitely
cover
multi-agent okay I mean we can be very
brief about it so it's it's anyway I
mean this is related to the grain of
Truth problem it's it's uh too great not
to mention at Le sure sure okay and then
finally of course any philosophical
discussions about AI that might arise
from these both Technical and
philosophical considerations that we're
discussing here um okay so this sounds
like a pretty good outline
yeah um maybe we should add for the
people who are here for the language
models that I will also talk a little
bit about LM but don't don't expect too
much but one recent one recent paper
which really ties it nicely together the
Solomon of induction and L&M um
so sure okay great um all right so why
don't we uh go to the next page and uh
why don't you start us off with uh
describing to us lass's rule let's start
with something super simple uh
well maybe just start with even simpler
frequentist
frequentist this
predictions I mean we need a notation at
this setting anyway so we have a
sequence X1 X2 X3 and so on and for
Simplicity we assume most of the time
binary but everything can be extended to
finer
alphabet um more or less
straightforwardly and to larg alphabets
that's usually I leave to the
mathematician because I think it's AGI
irrelevant um it can be mathematic was
interesting okay so I also use
everywhere the abbreviation X1 to n
which is just the sequence
X1 XM okay so let's assume they drawn um
IID so from a
Beni Theta process right and Theta is in
01 one so that's a biased coin if Theta
is not equal half it's equal half is is
a Fair coin and um we want to I mean
most of the time in statistics you want
to do induction you want to infer the
unknown parameter right and um well how
do we do that well we count the number
of
ones and binary I can just take the
sum um
um wait a second so assume we have seen
K once and then n minus
k n minus K is of course the number of
time steps where um XT is equal to zero
just the complement of course okay and
the KNE frequency estimate would just
estimate Theta as K divided by n and
from the large of large numbers we know
that it converges to let's call it Theta
0 if the sequence is exampled
from well I ID from P Theta 0 okay um
though long so good um most of the time
I will be concerned directly with
prediction rather than parameter
estimation um
which has the advantage is that
sometimes the parameter estimation can
be harder than the prediction for
instance if you cannot uniquely model
class you cannot uniquely identify the
parameter you may still be able to do
predicting prediction well so it avoids
a lot of complications in more
complicated classes here in this simple
boli class there is no difference so the
probability um under parameter Theta um
that the next symbol is one given the
history right um this is just Peta so
the predictive distribution um is the
same as as a parameter so so it's the
same
okay um so why is this bad okay and this
is where laas sort of comes in um so he
considered the problem of the sun rising
so he was at a certain age I don't know
how old you know I don't know maybe 30
years old and um so that means he has
seen the sun maybe Rising 10,000
times H and he asked about what is the
probability that the sun will rise
tomorrow again I think he had another
estimate where he estimated that the
world had been 4,000 years old according
to the Bible and um so maybe around a
million days yeah so you have even more
data that the sun rose every day so
what's the probability of the sunrise
tomorrow okay let's look at the data
sequence the sequence X1 up to you know
X say a
million yeah they're all
ones okay so K is the same as n so we
take the frequency estimate k / by n
which is one so we would predict that
the probability the sun will rise
tomorrow is identically one so we are
absolutely sure that the sun will rise
tomorrow and that feels of course way to
overconfident and he asked um how can we
come up with a prediction which is more
reasonable so it should be something
close to one uh but not exactly one and
um so let's derive La plus rule maybe
let's I mean I present you the end
result the end result first was that he
says we should
predict this probability by the way I
notation wise one to the million means
concatenation of of a million ones is
that is that right your
exp okay okay not lital expon
exponentiation okay I yeah yeah the
upper exponent has often multiple
meanings yeah I see okay I I I I
originally tried to correct it plus
because I thought you uh were looking at
numbers but I realized now it's just
concatenation so let me fix the fix the
Whiteboard now okay good good good um so
and he said instead of um using K
divided by n use k + 1 divided by n + 2
and um if you plug in K to be equal n
that would be n + 1 divided n + 2 which
is 1 - 1 / n + 2 so if you
uh assume the world the sun rose a
million times he would say the
probability the sun rising tomorrow is a
roughly not Rising tomorrow is roughly
one over
million and at least that's not
implausible right um the probability
cannot be much higher right if the
probability of and we remember that was
at a time where people had no idea um
about you know the sun being a fusion
reactor and exploding at some point in
the Supernova and these kinds of things
so this I model was at least not totally
absurd let's phrase it that way and um
it cannot be much larger than one a
million because if the Sun would rise
you know or fail to rise you know more
often we would have seen it already um
so it is sort of um a lower up about
depending how you view it but you know
maybe it could be even closer to one and
you could argue about it but now let me
give you the derivation and that's
really beautiful and I think everyone
should know this I mean it is really one
of the most basic applications of B
inference and the most beautiful one
though we don't know this parameter Teta
and while frequentist deal with this in
their own way but the basent just says
okay we have an uncertainty over this
prior Teta and we also model this by our
probability this is not a sampl
probability but this is subjective
belief probability or epistemic
probability okay usually I use the
letter W but you can also use P or
whatever you like and um um the
indifference principle
um um tells us if we don't know anything
we should assume a
uniform Theta is continuous parameter in
the interval 01 so a uniform prior would
be just equal to one okay so let's let's
let's just back up for a second because
um I don't know if you've already kind
of alluded it to what you said but I
think one thing that might be puzzling
about this if you haven't thought about
it before is oh if um like what's wrong
with assigning probability equal to to
one right because I've seen it a million
times before rising and so uh if I were
just to obviously use the the the sample
estimate then of course um uh for all
past observations the sun always Rose so
I should just kind of duplicate that
that estimate right like what um just
what's your what's what's wrong with
that okay first give you example more
close to home right um I
uh uh have a coin right which could be a
Fair coin or it could be a coin which
has two heads okay um I flip it a 10
times
right let's say 10 times and it always
comes
uphead are you 100% certain that the
next time is
head that's right fair fair enough fair
enough there there's there will a small
CH there's right now you could have had
a coin that had two heads on it or you
could have just gotten very lucky with a
Fair coin right so so so uh exactly yeah
so in this case of course the
probability is 2 to Theus 10 right so
the probability of it being the Fair
coin is very small but maybe let's put
in the in the mix a coin which is
heavily biased towards head right you
know has a 90% probability of head right
and now you see 10
heads well there's actually I don't know
the numbers now maybe there's a 50/50
chance it's a 90% head coin or the or
the or the full head so so you should
always and um you should always Reserve
um especially if you allow more complex
models um the probability that
something so everything so this is
actually a general principle everything
which is not logically excluded right or
by physical laws but even physical laws
may not be 100% certain right you should
assign a nonzero probability to it right
so to the event um that the sun will not
rise yeah it can happen right
why not right so you should assign at
least a nonzero probability and frequeny
would assign a zero
probability so they're just
overconfident you can you can view it
from a betting perspective right the
Dutch argument how much would you bet
right um you know against or towards
that the sun will rise or not of course
I would easily bet 100 to one that it
rise tomorrow right th to one but I
wouldn't bet sort of you know a billion
to one or whatever right maybe um
because I mean with Sunrise you maybe
then we all dead right so we need we
need
maybe anyway never assigned probability
zero except to logically inconsistent
events sure I
mean okay great yeah and I think that's
now a good segue into uh talking about
this uh um PRI uh assigning a prior
because that's
exactly therefore assigning uh weight to
all candidate hypotheses that aren't
ruled out by the data exactly so if we
had just two is Right Fair coin or
always head it would be just and at
prior we have no idea we would say with
50% it's always head coin and with 50%
it's a fair coin and then deal with it
but let's assume here um you know we
have no idea about this buyers of the
coin so take a uniform PR okay okay sure
sure
so now before we continue Let Me Maybe
present you paas rule in the general
form you can present it in many forms uh
the most useful form is the following
let's assume you have a class of
hypothesis hi
IAL one 2K or so um what does it mean so
these are Point hypothesis and they're
mutually exclusive so here what we mean
is that the probability of your data X1
to
n under some hypothesis I has a certain
probability distribution so for instance
H zero could be fair coin right then
this would be just one half to the n
uh age one could be all heads then for
the sequence all ones it would just be
one right so um so so this is just um
the hypothesis is just a probability
distribution we only care about
sequences here over sequences here okay
um then we have a
prior or maybe at this stage I use the P
so that is more conventional over the
hypothesis um so if we had sort of Fair
coin where head coin right would be half
half or something like this and I ask
what is my posterior that's my prior
belief what is my posterior belief in
this hypothesis after I have seen data
okay and base rule says you should take
your
data uh sorry the the likelihood
function and you multiply it with a
prior and then you need to normalize it
so that it's a prop probability
distribution and this normalizer um
let's call that P
of x 1 to
n is just the marginal
distribution over all this hypothesis so
that is called the pent evidence or the
marginal
distribution has many names um uh
partition function um okay and I mean if
if you flip it around um sorry just
inter sorry on the left hand side I
missed something a posterior here of
course yes that's right I was say that
yeah X1 to n so if you flip this if you
flip the denominator to the left hand
side you see it's just P of H given X is
p of time P of X is p of x given H * P
of H which is just the definition of
conditional probability so there's near
really not much to it okay but so that's
the great thing if you're basian that's
essentially the only thing you need to
know and you you just always you know
you think about your prior you come up
with a model class and then you just you
know crank based rule right so maybe
just to say this in a few words right
you you start with some um well your
prior is your set of initial credences
as to uh How likely the individual
hypotheses are in this case there's a
hypothesis for each value of the
probability that the coin uh produces a
one right so so each hi is is is the
Theta um and then the likelihood is just
is just a computation How likely the
data is given that value of theta and
the posterior is saying well what is my
uh new belief in the value of the
theta's condition on the observation I
just made and that basically by the
rules of probability Theory this is what
Bas uh rule tells you uh how you should
update your your your
probabilities exactly yeah so now let's
instantiate it so this is completely
General um whatever your model and
there's no I idea sumptions or something
um or stationarity or Markos or
something so that is completely General
but let's go back to the uh to the base
uh to the to the laas example so here um
well the class we have not a class of
finally many hypothesis but continum so
the only thing that changes is that the
sum is replaced by an integral okay um
and the
hypothesis class is now you know H Theta
or just Theta with Theta in
01 okay um and um then my likelihood
function on to n under H Teta or just
abbreviate T is okay so let's assume
there are K ones as before and N minus K
Zer okay so it's an IID model so this is
just the product over all P of
XT T = 1 to n okay what is the
probability um over one well the
probability of one is
Theta and how many ones are in this
sequence okay k k and the probability of
zero is 1 minus Theta and there n minus
K zeros in the sequence so that is my my
model of a buyas coin okay and now uh
the prior as
before well it's up here up here
okay so now we compute the posterior
before we compute the posterior we have
to compute the denominator which is
always the hardest part sometimes it's
impossible and you know they're all all
kinds of very sophisticated tricks to
still compute the proc without the
normalizing constant um and here it is
very easy to do roughly speaking it's
also a rule of Thum if you can compute
the denominator you can compute all
other quantities of Interest usually EAS
a rule of thumb and we will see we can
actually avoid even looking at the
denominator um so um so now let's
compute the marginal distribution so the
denominator the is according to this
formula
integral
over the likelihood times the prior so
that is just in this different so that
is integral 0 to one Theta to the K 1
minus Theta to the N minus k d Theta so
just one this is the likelihood right
the um in the in the
integran yeah the the integrant that is
a like times yes yeah yeah so I just
wanted to reflect that in the notation
just to be pantic here uh yeah that is
the same as P of x given H Theta yeah so
this should be a conditional on Theta I
guess yeah yeah I mean I have to put the
so you can compute the integral and this
so I I and this is the beta function
which is K of k + one and N minus k +
one and the beta function is just
product and ratio of three gamma
functions but let's just skip over this
yeah so so form essentially okay and the
gamma function for integer values is of
course you know factorials okay so now
we can compute the posterior P of theta
given
x 1 to n right which is just uh I mean I
can write it well okay let me write it
out um so that is a likelihood function
Theta the n 1 minus Theta to the N minus
K times the prior which is one divided
by this beta function which is a
constant
okay uh by the way I will later um
sometimes just use this notation with a
cross over the equal which means apart
from a constant okay okay so the
posterior um is also um this expression
and if you look
now um so if you here parameter Theta
which is between zero and one and you
ask about the posterior distribution
so before we have seen any data so for n
equal to zero well this is just the
prior and we are not sure what the Theta
is so it's just this uniform
distribution but now once we have seen a
lot of data um and assume it was a Fair
coin then K is about n half and then if
you look at this expression it would
look like this a little bit like a
gaussian um so the probability
concentrates around
well one half is the Fair coin and
around theta0 you can easily show that
if it's a coin with Buyers Theta zero
and the width is around of the order of
one/ square root n so um and then um you
know this converges to the point
estimate as we all expect okay um but
okay this gives you the posterior
posterior butas asked about the
predictive distribution okay so he asked
about what is the probability of x the
next symbol given X1 to n okay and there
are two ways of computing this so the
the standard way is we compute the
posterior um
and
um then we okay I should start it
differently so I ask what is the
probability of xn + one
given Teta so if I know Teta what is the
probability of next bit being one okay
being one is one and being zero is one
Theta okay but I do not know Theta but I
know I have a belief over Theta so I
multiply this with my posterior belief
over Teta and integrate over this okay
this gives me the conditional
distribution and it is very easy to see
that this is
simply P of X1 to up to n + 1 / P of x 1
to n so I could not do this you know
look at the posterior plug it in um you
know this is just the binomial multiply
with another Teta integrate it out blah
blah blah but um it is much easier to
use this expression because I mean if
you look at the conditional distribution
P of x given you know history well by
definition it is just P of X1 up to n
plus1 divided by P of x n + one okay and
the denominator we have just computed
above right this is this beta function
beta of k + 1 and N minus k + 1 and what
is a numerator okay let's ass let's ask
what is the probability of the next bit
being one okay so we now look at the
sequence which is X up to xn and then we
have a one so the next bit is one so K
which counts the number of ones is one
more
more okay so the numerator is exactly
the same formula but K has increased by
one so it's k + 2 N minus k + one okay
if you now plug in you know the beta is
a three gamas and the gamas are
factorials and everything cancels out
and as an end result you get k + 1 ided
n + 2 and that is laas Rule which is
very beautiful okay so let me um uh add
one
tiny thing so plus assumed a uniform
prior yeah and I don't want to go into
details um there is reasons for choosing
a prior which is slightly more uh heavy
on the Tails um that would be um a beta
one half one half prior if if if
somebody cares um I can write it down
but it's not really important um so and
this is called then the KT estimator
maybe that's important the KT estimator
meter and if you use this prior then
instead of k + 1 ided by K +2 you get k
+ 12 divided by k + 2 k+ 1 very similar
and sort of that is the modern version n
plus n plus one yeah n plus one in the
denominator
yeah n plus one yeah which gives a very
similar
result this something I actually don't
know why why would you uh have I mean I
I guess there's some optimality with
this uh prior so this prior is going to
look something more like as you said
it's GNA be yeah so there there at least
two different Arguments for it and yes
it will look like this so it's it's
proportional to Theta to Theus 12 1us
Theta to Theus one2 so it actually goes
to Infinity yeah yeah okay in and um so
there is two arguments one argument is
is though the uniformity principle says
if you don't know anything to my uni PR
but should I assign this uniform prior
over the parameter Teta or I can
reparameterize my problem assume um I
instead of using the parameter Theta I
use the parameter SI which is Theta
Square which is also which is also in Z1
right and say I just parameterize it
this way ah I should use a uniform
side but then it's a non-uniform because
I mean of the of the formula how to
transform densities so this uniformity
principle if you apply it nely is not
so-called reparameterization invariant
which is bad right and uh the uh the
jeffre
prior okay if you want to go there uses
the follow me uses the square root of
the determinant of the fissure
information Matrix but let's move on
right whatever that is right if you use
this as a principle for assigning your
prior which is a little bit weird at the
beginning but it's actually has
information geometrically has a lot of
meaning um then if you do a
reparameterization you still get the
same PRI I mean so if you start with
p and compute the determinant of the uh
of the P information moup s then you get
the appropriately transformed prior the
other justification is if you look at uh
redundancy bounds um or regret bounds
and you want them to be sort of Mini Max
optimal then this KT
prior comes out of this okay I like the
first I like the first uh uh reason
because you don't need to prove a a a
theorem or know something sophisticated
it's just it's an a prior sensible thing
to have
reparameterization in variance
yes so um people want to look it up and
out prior sure
okay they are the same but with the
different
justifications yeah so next maybe we go
to the general case of sequence
prediction right we essentially already
have everything yeah there's not really
much extra to do so now we start with a
model Class
M which contains distributions right
before it was you know age AG index new
or something like this so new of maybe
notation becomes a little bit more
complex right so X1 to n is some
probability distribution over sequences
okay and I have a class of these
distributions and from now on with some
exceptions I will assume that this class
um is I have to write it
differently um is countable m is
countable most of the time so that I
don't have to deal with um with
integrals and um I take a
prior over this class and then I call
compute the Bas mixer distribution
evidence or partition function or
whatever you want to call it because I
want to end same as before
sum
likelihood times
prior new in m and then I do predictions
in okay now also for con notational
convenience I predict XT
given up to T minus one so another X
less T is X1 up to
X okay so let's just back up a little
bit okay so a lot of notation was right
here so so first of all m is our
hypothesis space essentially um in the
previous example it was actually a a not
accountable space it was the unit
interval because we had a hypothesis for
every uh you know coin flip uh
probability of equal to one uh now we're
going to simplify accountable because
ultimately we want to get to a regime
where we want to uh say implement this
on a computer and of course the set of
programs is is countable so that's
that's kind of the Restriction looking
ahead why we want to consider things
that are countable correct exactly I
mean if if if it's uncountable then you
just replace as the sum by an integral
as before and the prior is a prior
density um but you know I don't want to
constantly deal with the two cases
account sure sure and and of course and
and uh I think maybe just one step for
clarity before we start uh
uh um start evaluating these these uh
quantities on actual sequences really
your prior is is without writing um
again it's evaluation inputs you're
you're saying my prior what you as see
here is say some sign some weighted
sum uh I think in your book you use
maybe a
subscript yeah you always use the word
prior solomonov used the word a priori
distribution um so um but let's not even
call it a prior I mean if you want call
it a priori distrib the prior is W of
new that's the prior and the Cai is call
it ban mixture call it Solomon of
distribution later call it Universal
distribution call it Bas mixture call it
basan evidence call it partition
function don't called prior so it just
to make our terminology consistent so w
is the prior and C is this mixture over
the measures in M with respect to that
prior yes okay great okay I'm happy with
that terminology okay um okay let's
let's well okay and maybe one more
comment so you start with this mixture
and the formula you just wrote here well
it's just the evaluation of that mixture
on a sequence of length n but what you
were about to write is how you're going
to update mixture using Baye rule
essentially
uh sure but yeah actually I mean you
would update the prior to a posterior
right but as I said I want to skip the
posterior and directly consider the
predictive distribution yeah I see what
you're saying yeah and there is no real
update so of Base does all this under
the hood right yeah so it is just you
have you mix the distribution and you
take the ITI of of so again let me write
it down of X1 up to T ID by of X less
than T and you could write it as an
integral over you know posteriors and
like blah blah blah and so on but you
know this is all gone now um I from now
on I only consider predictive
distributions maybe at some point the
posterior will pop up again but mostly
I'm interested in prediction and not
induction yes I see basically yeah I
mean this kind of came up also in our
llas example you could keep track of the
intermediate quantities in terms of the
prior and the iterated posteriors uh but
that all gets absorbed into uh under the
hood as you said when at the end of the
day if all you care about are these
predictive distributions that that
that's implicit in everything but you
never need to explicitly kind of keep
track of it but it's there if you wanted
to recover it exactly yes yeah okay
great okay good so now we have this
predicted distribution and so before in
our very simple model class we showed um
that this converges I mean or this
predictive distribution was laass Rule
k+ 1id n plus2 which converges of course
light frequen is asmol to the true
parameter theta0 okay now we have made
no assumptions about these news about
this probability distribution so one
could be for instance a distribution
which um is one on the digit of pi right
and zero on all others so it's a
deterministic uh environment which
produces a digits of pi right and
there's no or it could be Z one two Z
one four zeros one or something so
anything you want um so there is no no
notion of convergence to a parameter
anymore um there is a sort of parameter
underlying the new we could talk about
it but as I said I don't want to but we
consider the predictive distribution so
we can still ask questions like assume
we know assume the data X1 to Infinity
is sample from them distribution mu and
the true distribution I call always mu
before it was Theta zero Theta Zer is
usually the true parameter and here mu
is always the true thing and let's
assume it's in the model Class M okay so
if we know mu so X sample from mu we
cannot if it's sastic cannot deter bits
like in in a coin flip right but we
could ask what is the true probability
of the next bit given the history okay
in the B example that would be Teta zero
okay but we don't know mu so let's use
the basian predictive
distribution for prediction let's use
this one instead because this we can in
principle compute okay and now we can
ask how close is this to the truth
okay so let's take a square
and so it would be nice you know if it
somehow could converge uh could uh prove
that it converges to zero um well of
course it will not converge to zero on
all sequences only on sequences are
sampled so maybe almost surely maybe
let's just say a few words because if
you haven't seen this before it's it's U
maybe a little bit uh abstract so um so
mu is this uh true probability
distribution of of the sequences You
observe you don't know what it it is
what you do have is this mixture where
you you know decided what the weights
were in advance um yeah is there a how
do I say um Playing devil's advocate
here is there a is there a way to why
should I expect the C to converge to Mu
well okay I can give you some intuition
I could even present the proof but uh I
mean I want to move on um or maybe at
least some steps of the proof um so
first let me write down the result you
can prove okay so I mean okay you can
prove this result um and I'll come back
to in a second but you can prove
something much stronger and the way
actually you prove this convergence
result is VI the stronger result that's
the reason why I want to present the
stronger result okay so you cannot in
the IID case we could prove a rate right
so the side deviates from Theta zero and
the rate is sort of one over one square
n or whatever right but in the general
case you cannot prove a rate in this
sense anymore but what we can do is okay
first we take the difference
squared then we sum overall time
instances up to Infinity so we take all
the deviations and sum of it okay and
then we can
show um I fix it in a second that this
is finite okay well it's not finite for
every sequence but it's you know almost
purely or in expectation so we take the
expectation over this with respect to of
course the true
distribution okay so now what we have
here is we have an infinite sum of non-
negative quantities which is
finite and the only way that this is
true is that this difference converges
to zero but since there's an expectation
in front this convergence to zero only
almost surely so why does this bound
hold right and that is uh Solo's uh main
result um which you proved in in 78 and
first I mean we have here and and by the
way this is also
not the the very exact formulation but I
mean it's actually true in this form but
okay anyway um so let's take some
abbreviation s t and Mite is of XT given
X less T I don't want to write this out
always and the same of course for M okay
so what you have here is you have the
square distance between
anxiety and
M okay you can show um that's a version
say of pin inequality that the square
distance is bounded by the K Divergence
between M and ex I give you a more
downto Earth sort of intuition for a
final class in a second but that's the
formal proof so the the square distance
is bounded by the Cal Divergence so we
have a sum over
t I mean this is super sloppy here and
lots of things are missing so the
expectations and so on so the Divergent
has a telescoping property so this is
the same so if you sum only up to n not
to Infinity then this is the same
as the K Divergence between
the X1 to n given IX one to
n um so I mean this telescopic property
is well known
and if we write this down um then this
is sum over mu of X I really didn't want
to go into this detail
Ln so let me quick and then you give you
the the more intuitive but that is sort
of the proof um so this is this and if
you look at the basian mixture formula
above here so you still have this slide
here the was defined as a sum but if you
drop from the sum all terms except mu so
we get mu of X1 to then do you see this
what I'm writing MH MH okay so I just
drop all terms except for the true
environment so there larg yep so now if
I bring W to the left hand side and to
the right hand side you see that mu
divided by C is upper bounded by 1/ W so
this one here is upper bounded by W mu
to the minus one okay MH that's from the
above inequality and and this sum so
this is now a constant and this sum is
just summing the probabilities over
arbitrary sequences this just gives you
one so this bound and there's a
logarithm don't forget it so this gives
the logarithm W mu to the minus one and
as long as the prior is larger than zero
then this is of course smaller than
infinity
okay oh I see sorry n n is fixed here in
your summing over all possible
sequences yes all possible yes this is
all possible sequence n for fixed n so
this this shows you that for a fixed n
this is bounded by this constant but
this constant does not depend on nend or
now I can let on the left hand side the
the N to Infinity because here I started
with s
Infinity let's called this s Infinity
but then I proved only that SN where the
sum is up to n but you know since the
right hand side is a constant
independent of N I can just once I'm
finished take the limit n to Infinity
the left
okay let me get the intuition so let's
assume m is
finite and
contains m m is not used up M elements
and we choose a uniform prior W of new
is 1 / M okay um what you're doing is
there is I mean this will be informal
now but you can also formally prove it
um so you're
mixing over
uniformly over your environment in the
class and you're making a prediction and
that is very close to awaited majority
right I mean the if the majority of
distributions want to predict one you
will predict one okay so let's assume it
is a majority voting which it is not but
it's close and let's assume the majority
is Right predicts the correct thing yeah
then we don't suffer any loss and be are
happy okay let's assume the majority is
wrong we make a wrong
prediction then we get in the next time
step we get a feedback this prediction
was wrong so we can exclude this from
the class if it's deterministic hard if
it's probabilistic soft so this class
got half so for every prediction error
we make we have the size of the class
okay once the class is down to just
containing one element namely move the
true
distribution we are done okay so how
many halfings can we have well we can
just have at most log 2 m halfings right
so the number of
Errors is roughly bounded I see so this
is the deterministic case where your
measure is concentrated on a I guess a
single the prefix of a single sequence
yeah yeah okay okay and log 2 m is just
minus log 2 W to the new to Theus one
so apart from sort of an la2 uh you get
the same result in the deterministic
case with uniform prior and finite
CL I see okay
okay and then you have to make it for
nonuniform prior
um you get these weights and and it
still the intuition goes through then
you have to go to stochastic um um
models and then I mean we don't really
use a weighted majority because we use a
weed mixture um so so there are
differences but the intuition is the
same sure sure sure okay okay um let's
just take a step back because uh okay so
this this gives intuition about that
bound uh but I guess the the the very
high level non-mathematical intuition is
essentially the let's go back uh one
slide here um what this what these
bounds are saying is that as you make
more and more
observations um your
mixture predictive distribution will
converge to the true one UHC for several
reasons one you assigned nonzero weight
to every possible hypothesis so you
don't exclude anything that was this uh
epicurus principle that we discussed
earlier when doing beian uh inference um
uh so that that's one prerequisite and
this uh the second thing that's
happening is uh as you just alluded to
as you make more and more observations
the ones that are inconsistent or
improbable with respect to Mu in general
get down weighted and the things which
are more consistent with mu get
upweighted and that happens in such a
way that ASM totically you have to
converge to me your your your your
predictive
distribution ex intuitively exactly
right I mean we can even write it down
like before so let me write it down here
so we can write down this sty of XT
given history as what I wanted to not do
anymore but let's do it anyway is new
the
posterior uh W of new given x l
t and then
times uh new of XT so you use the beian
update rule to compute those uh those
revised
um W's those weights and what you'll
find is that those weights go up for the
things which are consistent with me and
those weights go down for the things
which are inconsistent or improper
exactly and in in very simple cases this
posterior would just on the true
distribution it would converge to one
and all the wrong distribution it would
converge to zero that's right um in this
more complicated setting maybe there are
two distributions which are totically
consistent right right um all this so
about the the total weight on the
distributions which are consistent with
the data converges to one and those
which are inconsistent converg to zero
that means effectively in the simple
case where there is single distribution
um where it concentrates to the trth MU
and this sum just collapses and gives
you mu of um XT given x l
t um but proving this VI the posterior
in the general case um is hell um and I
this we will not talk about it so okay
what's what
next okay um so okay next uh let me
instantiate that I that was now I mean
before we started at the simplest model
class like you know buyer's coin now we
have a completely General framework we
can plug in any model class we want and
we have this bound right so let's
instantiate with two or three
interesting classes um which are
important because they are bigger so
more interesting but still uh tractable
so it can be computed in a path way okay
so you're going to look at now
interesting M's this family of okay yep
okay and um so
um the okay I have shown you this bound
on the last uh uh slide um if we have
and that holds for any countable class
but if we have a continuous class right
back to it and again you the proof is
hard and I don't want to do that um if
you have a continue class with d
parameter so let's assume M sort of is a
class new Teta where Teta is say a d
dimensional parameter okay
now okay and then you can show a similar
bound um there you have to make some
smoothness assumptions but you can show
a similar bound and the bound is then uh
Ln W of theta to the minus
one um
as
before
um but now this is a
density then because it's a density do
you have D
half
lnn term and this grows with Ln n so
this dominate so this constant could be
avoided and then you have uh the
logarithm of the square root of the
determinant of this mysterious fure
information Matrix plus terms small or
and which converge to zero don't worry
about all this the dominant term is this
one here and we just ignore this one
this is a constant this is a constant so
it's just the half l andn so the rest
you can't forget about it okay if you
have a continuous
class and um so and in the in the Beni
Teta case D was one and the bound would
be one half okay and the intuition is if
you have a continuous parameter um you
you could discr ize this parameter and
just take so we know that we can
estimate a parameter to accuracy 1 /are
of n yeah and to encode a parameter to
one/ square of n accuracy you need one
half log n Bits right so so that is one
way of interpreting this B so each
parameter gets discretized to the
accuracy which is needed and no more and
then um this gives you we haven't talked
about code length yet but will we will
get to that so if you VI it the second
time you will understand what I mean
with this anyway just just trust me so
this is the bound so for instance a more
interesting class in IID would be a k
Mar of model okay so that means that the
probability of xn plus 1 depends on X N
- k + 1 up to uh n so the last k um
parameters okay so how many parameters
are they right for each context here so
assume alphabet size is
X or barx right the context length K so
the
k x to the power of K possible
conditions right and then we predict xn
+ one and well you know this could be
you know out of X but they have one
probability constraint so that is x
minus one parameter so in a binary case
it would be one parameter if you have a
tary case it would be two parameters and
so on so that's the number of real
welded parameters you have in this model
class so our D is this one here works as
before we just take the bound you plug
this lightly larger D in there and
that's the number of prediction errors
you make roughly speaking okay nice
Class K
marov but if K is large you see it's
exponential in K and it's no good so
there is a class which I think everyone
should have heard about but uh ma sorry
are you making the point that in this
generalized bound you had above with
with d and and uh log n that U that D is
the for the K uh order Markov chain
that's the D that you use this formula
that you you wrote yes okay yes yeah
because that's the number parameters I
need to
specify that's right that's right okay
okay so that's a k Mark of
process um but now I talk about very
briefly something
context
three
waiting algorithm okay so what
this okay so what this does is um
we okay okay very briefly um but we need
it later if we come to the
approximations so what is this
essentially a variable order Mark of
process so what you're doing is now
instead of using
say two last
symbols you use maybe if the last bit
was Zero you maybe need another bit to
differentiate it whether it's 0 one but
if the last bit is one you're fine you
don't need to see further bits in the
past okay um so you look at these
trees and um these trees have of course
parameters right I mean sort of the
context is z0 you have a parameter if
the context is one Zer you have a
parameter and if the context is one is a
parameter you also have a number of
parameters okay so for fixed three you
do the same as before and what you get
is well D is uh just um the um the the
the number of parameters let's call that
the set Theta is the set of your
parameters and then it's just the size
of this parameter set okay nothing
changes okay for fixed trick
but if we don't know the tree what we
would like we would like to do a basan
mixture now over all possible trees
right maybe of maximal depth D or so
okay so um we just take the class of
trees so T
is trees
of death smaller equal than b okay then
we need a prior over trees we can do the
somehow so you can encode a tree in bits
and take two to the minus the code
length we will get back to that later in
a more General context three as your
prior over
trees you have of course you have the
prior over the parameters where you take
your either uniform distribution or the
KT one which we discussed before and
then you do this huge Bas mixture over
everything so the the thumb over all
trees of dep at M the sum well sum
overall once you fix a tree over all the
parameters which are in the
tree and then you have your distribution
which is then the
um well some distribution X1 to n given
the T and the Theta well the sum of
theta is of course an integral of sum
and then you get your distribution
whatever you would call
it okay so is this where this beautiful
fact comes in that okay if you were to
do a naive beijan update you have to
update you know this I don't know double
exponential count of Weights because
that's how how many trees there are but
if you only care about updating the
predictive distribution there's a very
nice
algorithm actually it is the you you can
update the predictive distribution
efficiently too but it's much easier to
update the joint distribution and then
take the ratio so even the joint
distribution is easy to calculate um if
you calculate in an online way and let
me just write it down because it's so
easy so yeah if you would do that I mean
the integral is easy to do and which is
just lots of local little laas rule but
this sum is hell as you said um there
are this class T is about two to the
two okay so now let's go to larger
classes and before we do that we have to
introduce comol complexity but I can do
that very briefly if you don't think
much about
okay so
um generally let's step a little bit
back um in science um we need a
principle which is called okam razor
principle so if you have two hypothesis
which are equally good describe your
data you should choose the simpler one
and there is no way around it sort of
without oram's razor there would be no
signs um Believe It or Not uh well it's
argued in my book and you know many of
my papers so I'm no time for that here
okay but what does simple mean we have
to need a quantitative notion of
Simplicity and we want one which is for
AGI purposes which is universal right
which is not sort of limited to some you
know nice classes or something like this
and color of complexity does that for
you so think about any object you code
it nely is a binary string I mean think
about you have a I mean now all data are
binary anyway right and you ask what is
the information content in this string
well if it's a string of all ones right
it's pretty boring right um but if it's
you know Pi it's a little bit more
interesting but you still I mean it's a
very easy description if it's a picture
from a camera there's a lot of
information in there and we can capture
this by how difficult is it to describe
um my data well we need a description
links well let's just take a programming
language as a description and you anyone
see or list or whatever want um or
abstractly we take a universal touring
machine because you know that is also
Universal description language and we
look for descriptions of our data okay
so let's take this Universal touring
machine or your list or your C compiler
whatever you prefer we look for a
program which if you run it gives us our
string x one to n okay um but there of
course many programs which produce a
string for the you know the digits of pi
I can WR print quotation mark one
billion digit of high quotation mark
very long program but they also shorter
programs and you want to okam raer ask
for the
shortest program hypothesis theory model
of our data so look at the length of the
program and find the shortest
one okay and the length of the shortest
program is called the
quor of X and that's it okay and um you
know I don't want to argue here why this
is a good measure um you know you can
read it elsewhere okay and we're going
to use that um what you can show is that
it is nearly independent of the choice
of the universal touring machine so if
you take code with respect to one
touring machine or you compare it to K
Prime with respect to a different
touring machine and you take
uh the supremum over all
strings this is bounded by
finite constant so if you have strings
which are longer and longer so even over
all
n if you have longer and longer strings
um still the difference is as a constant
which is the typical compiler constant
between compiling from say U to U prime
or from list to C and so on and I mean
we have our data is so much richer and
larger in AGI than this compiler
constant that you can ignore this
problem um second problem is the incomp
computability what you do now there is
okay this is looking for the shortest
program which looks like compression
okay so if we have data and we create a
self extracting archive which means it's
a compressed version but it always also
has the decompressor buil in what is a
self-extracting archive well a
self-extracting archive is a program if
I run it reproduces my data yeah so what
I can do is I can replace the kolf
complexity by you know the best
self-extracting the shortest self-
extracting Arch which are currently you
know can create with practical
compressors as an approxim okay um so
and how do we use this why do we care
about this here well it quantifies or
which is really great um but um so that
was for
Strings um if I have any other object
like numbers I can encod it in strings
right if I have a probability
distribution which computable right
there's a progam which computes it and
just this program so so any object o can
be coded as a bit string um so and then
the colol complexity of an object O is
just defined as the sort of some
canonical encoding of it and it just
drop it okay because I will now one yeah
I mean I guess uh we're always working
over uh countable things which is why
this is possible because of there's only
countable uh number of uh strings and
Turing machines so of course like but we
talking about probability distributions
by restricting to probabilities over uh
finite length strings that we're in
accountable situation yes for
probability distributions we only look
for computable probability distributions
now right that means by definition that
exists a program that means it's only
accountably many okay and then we write
K of new for a computable probability
distribution and that's used mu for the
class of comput probability
distributions okay and technically it's
lower semic computable semi
distributions but let's not go into that
okay um okay so now we have a measure of
complexity of a distribution and Oram
raer tells us take the simplest one but
aporus principle tells us keep them all
and we can unify these two principles
and say well you know have a higher
prior belief in the simple ones and a
low one in the complex ones and the same
with the posterior so don't rule out any
so we to choose a prior now before it
was left
unspecified now we choose a prior which
is two to the minus of
complexity and so that is monotone
increasing what you want and you choose
two to the minus K of new because you
want it to sum to one or at least to be
bounded by one and you can prove that
this is the case because a prior needs
to some to one or at least um not more
than one so we now have fixed let's it w
we have fixed the class to be all all
computable probability measures and for
the expert please forgive me that I'm a
little bit crude here um with some
things and we have fixed the
prior well and we can use Solomon of's
Bound for this so the Solomon of bound
was as Infinity was bounded by Sonet PL
in this so we we get the Cai over this
class let's call it caiu and the bound
was the logarithm
W to the minus one and if you plug in
this this is just K of new
*
ln2 so this is this is now actually Sol
is what he's proing okay
and yeah no no this is nice because this
is saying
basically um I
say simpler hypotheses have fewer
mistakes on average right right exactly
even more precisely if you have a
hypothesis a model which you can encode
specify in 500 bits then roughly
speaking Solomon of induction makes 500
prediction errors and then it's good you
never can tell where they could be at
the beginning that could be spersed out
but you roughly only make 500 prediction
errors and then it's good I mean the
real result is that you get closer and
closer you can prove sort of the number
of Epsilon errors is bounded by K of new
divided by epon square and blah blah
blah and so on right but roughly
speaking and that is also intuitive
right if I have an unknown World which I
need 500 bits to specify I need to learn
this 500 bits somehow by trial and error
right so I need to make 500 mistakes and
you can indeed show that it's the best
possible Val I think what's good to
emphasize because I I don't think I
appreciated this the first time is that
there are uh many uh priors you can
write because the only condition of
being a prior is just that each W new is
is positive right you want to assign
positive weight to any candidate
hypothesis and the bound you wrote a few
slides ago uh could have been any such
uh we could have used any prior and and
the C that we had was the mixture
obtained from that prior what's special
about the prior that you just wrote here
using the comor of complexity is the
fact that it has this sharpness with
respect to this this bound that that I
want you to maybe explain a little bit
what's the opt what's the optimality for
for this yeah so what you can show is
that this Wu of new yeah so you take any
other prior over new is computable I
mean the non-computable prior I mean we
cannot deal with anyway okay we take
comput fire what you can show is that
apart from a multiplicative constant
this W new is
larger which means that apart from this
constant minus l
right is smaller so if I take
Now log W new minus one then this is
smaller
than log P of new to the minus one apart
from an additive constant because the
log makes a
multiplic and this constants float
around anyway in complex you always have
comp sure from Conant this gives you the
best possible bound sorry what is this
this lower bound you wrote up to a
constant what uh that is so what's the
statement the statement is that if you
choose any other computable prior ah I
see it will be smaller than the
universal prior apart from a
const ah okay because because if it's
computable this is this is an intuition
I don't if it's correct but if it's
computable then you have to use a
program that's basically lower bounded
by the com growth complexity and then
two to the minus that is is smaller
right yes the proof right okay okay all
right I see okay this this makes this
makes sense okay I
see okay so so it is what if your data
is sampled from any computable
distribution let me rephrase it can be
the digit of pi it can be a pie wise
noner sequence it can
be a chaotic sequence or whatever as
long as there is
a program of B bits which computes in
stastically right um your your sequence
um solomonov will learn it in the
minimal number of errors this makes this
makes total sense now this this is this
is very beautiful yeah yeah
yeah okay so this was um a little bit
heavy maybe um there is a different
represent so this is called uh well
this
U um this is called the where's caou
here caou is the universal distribution
um but solomonov
um derived a different distribution but
which turns out magically um which is
equivalent and this different one is I
mean you know we had a lot of Machinery
now going on right and you know base and
then you know Comm complexity and and
all this kind of stuff there's a a
shortcut to get to this and I would like
to present this shortcut in a short way
so what you're doing here is is let's
just pause this this SIU is the Solomon
of Prior
right that's the Solomon of there two
different definitions and versions and
and this is one one of them that's right
okay yeah okay I'm usually attribute the
other one more to Solomon of but sort of
he came up with both in a sense ah okay
okay so um okay so the other one is you
take um a universal touring machine
and which has an input tape and an
output tape and by the way I'm skipping
over so many things you need monot
machines and so on so but you know this
is all precisely in my old in my new
book um so um we have we have an input
tape and we
sample a uniform random noise so Fair
coin
flip on the input tape okay so this
touring machine sometimes will do
something sometimes not so there will be
a probability distribution on the output
tape okay and let's just call this
distribution M of X whatever that is but
there is a probability distribution of
output T okay and it turns out that m
ofx is the same as s of
X again you can be more precise either
with a multip constant or for every M
that exist the universal touring machine
the s so they have a whole paper about
this but essentially it's the same I
will not prove it here the proof is you
know long and difficult um I give you a
little bit more formal definition of
this what does it mean actually so we're
looking the input tape is bits but they
are sort of Interest programs um you can
ask a question in a second so so this
this p is input bits okay on the touring
machine and we then run the touring
machine okay on P and then it outputs
something if it doesn't output X1 to
n we don't care we only look at programs
which output X1 to n okay so assume
there's one program which outputs X1 to
n and only one because this program has
length L of
P the probability of sampling this
program from Fair coin flips is just 2
to the minus L ofp
right okay but there will be many
programs which output X so we have to
sum over all of these programs um to get
this output prob so that is this is
exactly the same as sampling infinite
random noise and piping it through a
universal toing machine this is sort of
the formal formal definition here and
then um these programs don't need to
hold the star indicat that the program
don't need to hold fine and um yeah and
you can show highly non-trivial that
these are equivalent and that is really
nice so you can so here we only consider
deter programs predicting strings and
mixing over them with a prior which is 2
to the minus L
ofp but the intuition roughly speaking
is that these
stochastic environments are sort of
living in the convex Hull of the
deterministic ones so are implicitly
already included um in the determin so
you only need to mix over the corners of
this infinite Simplex in order also to
get the middle one but I mean this
intuition is an intuition but it's stly
speaking it's not right but anyway the
statement is correct so we we we defined
Salomon of uh Solomon of Prior the
Solomon of mixture distribution in terms
of Kor complexity you gave this
alternative definition what Solomon of
induction essentially is it's it's it's
the basian sequin sequence prediction
when we start off with the Solomon of
Prior right and it has optimal
theoretical guarantees that's what's
nice about the Solomon of Prior okay
okay so why don't you describe your the
the two other things you wanted to
discuss in this section so this is all
you know good be I I covered small model
classes and then this Solon of class
which is I mean you know incomputable so
you canot really use it in
practice um um neural networks are all
the r these days and large language
models
um what they're doing is when you're
training them you're minimizing log loss
right okay so um so if you have if your
data set which is a long
string
okay um you have this language model P
which is parameters by you know this
weights right and you predict um the
next uh symbol given the history of
course they have a finite context so
it's not the whole history but you know
that's fine okay and um trining means
minimizing log loss so you take the log
loss minus right and
minimize over
Theta and the argument gives you then
you know the optimal one of course you
do CR descend you may not get the global
minimum and so on but that's what you're
doing okay so um but this is the same as
maximum likelihood right I mean you put
the minus away and without the lock so
this is the same as the maximum over
Theta P from X ah uh sorry um you you um
sum here of of course over all time
steps I mean you train on the first
token I mean you you you you train on
all the tokens right um up to
n um you pull the sum into the log which
gives you a product and the product of
the conditional distribution The Joint
distribution that's the same as as
taking the likelihood function and
maximizing this okay so minimizing uh
log loss um uh in llm so maybe I should
have
heading here um is the same as your know
maximum like estimation okay and um we
know that I mean for simple model
classes of course these model classes
are not simple but if the model class
were simple AR marks that would converge
uh to uh the true parameter um assuming
of course um that um you true parameters
in in the model class so that is the the
the class uh the the llm class right
that the lmm can represent it okay I
mean there is really I mean you know
lots of assumptions here you know lots
of shortcuts very quick okay so but if
you would do that um so you have some
sequence say you know B only one3 you
train your model on a b 1 third sequence
then you stop training and then you use
it for
prediction if everything goes well it
would then predict you know B only one
third right
um but
this view uh is maybe not the the the
most appropriate one because these
models are trained on a lot of data
right you know and you know there's a
chunk of maybe you know Fair coin flips
and then there's a chunk which contains
the digits of pi so more plausibly
actually our data set looks like X1 to n
and then we chop it
up so you have multiple data sets
um and um you know the first one is
maybe you know as I said you know little
over half the next one is Wikipedia page
and so on so that's more realistic okay
so how can we model this so let's assume
that um so so this correspond maybe to
some parameters th K right um but let's
assume so this
is let's assume that this K let's don't
talk about Teta yeah this Cas is itself
sampled from some prior distribution
let's call it w
of of k or something like this okay so
put a do here right some some prior okay
so you so you view the real world data
as okay first I pick a website and then
I train on this website right and then I
pick another website and this website
one website could be Pure Noise the
other website is Wikipedia the third one
is some program and so on okay so that
that's a better of the data okay what
does it mean sampling K and okay and
these these ones these um
x one to n k is sample from the
distribution say new K
okay so what does it mean first k Sorry
W is the weights of like you could think
of these uh I'm thinking of these cases
like indexing different documents right
and W's the weight of different maybe
maybe they just be form distribution
this case okay okay and then new of K oh
I see new of K is the the the language
model of language within that document
essentially yes I mean it could in this
case it could be deterministic right
just the content of this website right
or it could be sort of if it's a if a
agerate if you take sort of K2 index
over okay here are all Wikipedia Pages
here all Twitter pages here all programs
then it could be sort of real
distribution but if you find more it
would be deterministic it doesn't really
matter at okay sure sure sure sure okay
okay yeah the point
is you sample K somehow and then you
sample X from new K so that's an
approximate model of what what we where
our data comes from okay so what does it
mean is okay what distribution do we get
out so we get we take the new K now
First We Take the K but we take it as
probability w k and then we sample our
X from new K so the probability of
actually getting oh
if K is discret it's a
sum it's something like this it's a
mixture distribution right yeah so the
whole worldwide web data is better
represented as a mixture over different
distributions right sure sure okay so
that is our training so the
distribution or data is roughly speaking
sampled from something likei okay
rather than a p Theta I mean from a very
abstract level there's no difference but
that means if you train on this data the
language model if it has the capacity to
represent s will then learn Cai okay and
if we then use it for
prediction it will be a Cai
predictor okay sure have a mixture but
it means for instance if we take the Ben
T class we give the model we sample ABI
one half sequence train then we sample
ABI 0.8 sequence we sample then we
sample 0.1 sequence and we sample what
the language model should converge to it
should converge to the basic mixture
over this which is a plus
Rule and it does but we tested this and
it perfectly does it okay which is
pretty amazing I see I mean it okay that
makes a lot of sense in the bruli case
just to make this more contrete in the
linguistic setting this would be
something like okay suppose for
Simplicity you have two domains you have
uh children's stories and academic
articles and basically as you sample
more and more tokens if it's really from
a children's story then the prediction
should be more and more children story-
like and if it's more of a scientific
article it should be more and more
scientific article like right that's
just just the linguistic way of
reformulating what you just said in the
beri case right exactly and we tested it
Beyond benoli yeah we didn't test it for
language because everything is modled
right we used piecewise IID data which
is a little bit more difficult than IID
also works okay then we use this ctw
distribution this highly sophisticated
distribution which I introduced before
and the model also perfectly mimics the
ctw distribution in context this is
pretty
it was even better than the ctw which
theoretically cannot be the case but
then we found some bugs some
inconsistency how we train and how we do
the inference so we fixed the bugs and
you know then it was equal performance
but really funny so this papers out
there um so um people can read about it
and then we got ambitious I mean then we
thought okay you know what we really
would like to do is Sol to predict the
solom of distribution but is
incomputable let's assume we can sample
from this
distribution Trin a large language model
on data which is sampled from Solomon
of's
distribution and if everything goes
right then the model would be able to in
context emulate solom of's distribution
which is a perfect predictor for
everything okay sure actually just one
thing I I'm trying to think what could
have gone wrong and it because why is
this uh significant and it sounds like
to me what could have gone wrong is that
the mixture does not update in the way
you expect it so it could have been
rigidly 50/50 with this domain or that
domain no matter how large the context
is right and and and uh I mean is
that way it could go wrong yeah one way
could go wrong yeah yeah yeah but but I
mean the way it would technically go
wrong is that uh Transformers just don't
have the capacity to represent these
mixtures right the assumption is always
that set are Zer is in the class and um
you know that a Beni Teta for a fixed
Teta is in the class is very plausible
because just IID the plus is in the
class counting the number of ones and
Counting zeros uh yeah I mean it's
should be able to but they're not so
good at counting and also the context is
fin but it still work yeah but these
more complex classes um it is up not at
all clear that um the architecture of a
transformer is Rich enough to represent
even this mixture distribution I see
what you're saying speak of the Training
Method gets you there okay although
although language is a very complicated
uh uh I guess you know in some sense un
potentially un unbounded or no no no no
fixed order markof process right so it
it since it can represent language well
maybe I don't know how right how okay it
could represent other things but okay
anyways just just some offthe cuff
thoughts um okay anyway so we got to
ambitious and thought wow that would be
amazing you know but of course we cannot
even sample from Solomon of
distribution but we did you know we we
we look we looked at some tiny
programming language where short
programs already output some interesting
strings and you sample from it then they
train the language and you know we get
some positive results you know it's very
hard to tell is it great or is it just
good or is it it's more than just random
garbage so it does something uh and and
we are happy with the result but for
these smaller model classes up to the
ctw and the PTW it was perfect and with
the Solomon of it also does something
reasonable so you know maybe you know
this is a way to go to um so Amic we
don't need any data right um so all this
is artificial data it's all the trained
on artificial data and then um the model
does all the the actual learning from
the real data in context which is at the
moment veryable anyway people you know
extend the context to millions and try
to push everything into the context um
I'm not so sure whether this is really
the way to go
um May maybe just to clarify I think I
think maybe one way to to say what I was
trying to or a better way of saying what
I was trying to say earlier is um so you
going back to the slide you you train
your Transformer on this data uh and you
wanted to emulate the mixture
distribution which is this this s right
here and one way to evaluate how well it
learned it is precisely
to
uh generate longer and longer samples
and see that the rate at which it conver
you know converges to the the true Mew
uh obey it obeys the right properties
right yeah yeah that would be one to
evaluate but in this case we could also
just I mean for at least for the ctw the
Beni we could directly compare the
distribution to the mixture because we
have the mixture
right I mean the practically the
practically eval is always against the
truth of course right of course yes yes
yes but but the the the scientific
evaluation we could just evaluate
against the site itself oh I see right
you could just compute the probabilities
directly from the model outputs and
compare it to to the me in this case
yeah oh fair enough okay so um so we're
nearly done um with uh the prediction
part but sort of as an um as a bridge to
the agent part um let's consider
loss functions and sort of actions but
let's still call them predictions
because there's a major difference
between the agent case and the
prediction case but the loss function
still sort of can fit in here so um l
f um so the the protocol is similar to
before um we make a prediction
um but let's call this prediction now YT
okay then we
observe XT okay then we
suffer loss
XT comma YT okay uh the important point
is that um we do not see XT before we do
the prediction okay um and um in general
I mean I call it prediction but this
could be in any other space so if XT is
in X YT could already be in a different
Space by um and so for instance say you
do weather forecasting uh but you can
say you know if if it's rainy um I take
my umbrella and if it's sunny I take my
sunglasses something like this so the
the prediction or action is actually
taking umbrella or taking sunglasses or
they live in different spaces of
different size uh um different sizes
even um so that's all already included
the important point is that your
prediction or action whatever you want
to call it does not influence the
environment still not okay so you your
action taking umbrella you know or
sunglasses doesn't affect the future
rathera I mean you know know there's a
butterfly effect but you know we
assuming it there's okay so if you do
this then um what we the best we can do
is so we have the loss um we suffer but
we don't know M XT okay so let's just
take the
expectation yeah over XT so the history
is fixed with respect to well ideally
the true distribution but I mean let's
take row some distribution okay so
that's the expectation only over
XT and then we want to minimize this
loss
see okay and let's call this the
RO uh predictor okay so the RO predictor
minimizes roow expected loss now
standard set of nothing special so what
is the real loss I suffer with the
strategy well the real loss
is well
whatever the outcome
is
uh okay whatever the outcome is but the
outcome is of course uncertain the true
XT is sampled from my true environment
distribution mu mu is always the true
environment
okay so this is my true expected loss if
I use
strategy YT
row so so expectation with respect to S
above that's with respect to your own
model of the sequences not the true one
well buff it was the expectation with
dist to some row not specified at the
moment oh okay I see okay okay but this
is not the true expected loss true
expected loss I have to take the
expectation with to the truth right sure
sure I use I use the row expected
predictor evaluate it with respect to
the truth of course that's right that's
right yes yes so now I take also the
expectation over the history so I just
take the expectation
here now I some overall time
instances uh let's sample
in um yeah I probably don't need really
I can't do use Infinity okay to use your
weather analogy row could be like how to
best choose your your uh um weather
prediction say in the United States and
then maybe now you live in London and
then mu is the London uh distribution of
weather right so so sort of you could
incur loss because of the mismatch for
example yeah yeah yeah yeah okay so um
let's call it loss of so loss of row is
the total loss lifetime loss expected
loss with respect to the true
distribution over the for the row
predictor okay um obviously by
construction if I would minimize with
respect to the true distribution that is
the optimal thing to do right this is
smaller than the loss of row right
yes of course so if if I minimize with
respect to the to the Criterion right
you know then of course this is better
than doing anything else okay that's
fine but again as before we do not know
me so we have to do something else right
and you could be a machine learner and
learn M somehow or you a be and you just
repl the M by a Bas Mak side
okay so L
moon is the best you could ever achieve
if you know
me and let's
look if we use
Cai so we use the we minimize the Cai
expected loss and compare these two
losses
okay and now I have to do a little bit
of a funny trick
um I take the square root here and the
square here because otherwise I I can
get a bound but it's ugly so I just
don't compare the losses but the square
of the losses okay just the difference
is called the helinger loss okay um and
oh no I don't take any
Square okay and ask well if this is
bounded by a constant for
instance then I would know if the
optimal muos is finite then the optimal
cyos is finite which is great right
remember over infinity many steps if the
loss of mu sort of has a certain frequen
see you know maybe 50% or something then
the cyos also at the same frequency
assuming there's a finite bound and
amazing thing is there is a finite bound
finite bound as usual is the Ln W of mu
to the minus one now with a square
root is
there how do I
say and for the specific case of Solomon
of distribution right is this is this
loss like I'm surprised it should be
even finite in the first place right so
it's sort of like if it's like if you
have a for example if your loss is 01
accuracy
then this loss function will generically
have an infinite sum over ones right is
there some
discounting maybe I'm look different
assume you want to predict say assume
the weather is uh
Bly 0.7 or something like this okay yeah
ah okay sorry keep going yep M and you
have a loss function and you choose your
umbrella your sunglasses of course you
often get it wrong right mhm so you will
suffer a loss right um which okay well
actually so I need the nend because
that's Infinity right so I that's what I
was that's the point I was make yes I
need up to n and then this is n and this
is n um but then I can yeah sorry then I
can take the limit end to Infinity on
the left hand side sorry
yeah okay thank you
and n
n n
yeah yeah Essen this is like a like a
regret bound essentially right yes
except that there's a we s sure exactly
yeah yeah yeah okay you're right right
yeah yeah but you can convert it over um
so but this is the best way way to see
it in the simplest way and the fastest
um a very neat bound um okay so that
shows ah I should have this bound holds
if the loss function um um is in 01 so
it must be a bounded loss function any
bounded loss function just scale it but
if it's unbounded more complicated okay
so not not cross entropy okay yeah sure
something like that yeah
so the nice thing is that Solomon of
prediction is also optimal in in this
sense with respect to any loss function
you care about not just the square
distance between the distributions or
the log loss or something like this so
just just
maybe make one remark yeah because of
the optimality that we discussed earlier
which is that if you have any
computable
measure then you're going to assign less
weight up to you know constants than the
Salamon of weight which is 2 the minus
color of complexity then this upper
bound becomes larger because of this you
know log of a reciprocal right so in
this sense the Solomon of Prior gives
you the best convergence rate and also
the the the optimal regret right which
is the the minimal regret right yeah
this is this is amazing this is great
yeah it
is
okay with a nice or maybe we can start
the next section or you can cut it if
you like so let's let's end um or start
with a a nice quote um of Gregory uh
sorry of um of Marvin
Minsky um uh when he was quite old 2011
and he never worked on colol complex
Solomon of induction but there was an a
panel discussion with him and Gregory
chartin and some others and it was one
and a half hours and the last statement
this whole conversation by Marvin vinsky
was and I'm paraphrasing I don't know
exactly but pretty much um Solomon of's
theory is a beautiful theory about
prediction everyone should know
everything about this Theory and spend
the rest of their lives working on it
wow
okay okay noted so why don't we now
start on part two of our outline we've
let's just maybe quickly recap what
we've done uh part one was called
Universal prediction and we explain how
well there's there's the bean setup
which tells you how to do prediction
once you update your priors to get
posteriors that are now data informed
data revised uh we introduced color of
complexity so we could talk about the
Solon of mixture distribution or Solon
of Prior however you want to call it um
and that gave us a prior that had
optimal convergence properties both
respect to prediction and loss um and
then we also discuss some interesting
model classes um but what we've left out
is action planning right because at the
end of the day intelligence requires uh
interacting with the world those actions
will influence the world and so we want
sort of the action version of this and
that's where the universal artificial
intelligence comes in and this is where
your your contribution comes in right so
is that is that a fair summary of where
we are yes I mean my contributions I
mean apart from theom of the original
bound everything else I told was also
sort of a lot of my contributions and
there's there's much more I have done
there's this paper um a philosophical
treaties of universal induction there
are so many other bounds and interesting
insites you can have right where
unfortunately there's never time to get
to this um so but I mean this paper in a
lightweight form and there's an older
paper in a more heavyweight form
contains sort of a summary of all the
other stuff related to Solomon of
induction itself yeah but the major
contribution is indeed um uh to to the
active agen Cas yeah she of course your
your books will be a proper
monograph giving citations and
references so people who want to know
more about the contribution isues can
can refer to that um but okay great so
maybe should we just get started in in
section two um yeah we're pretty
open-ended I guess basically we we want
to adapt how I say kind of technically
we've I my sense is we've done uh a lot
of the work the planning part is sort of
at least at a high level a modification
of that and that okay now you just add
this uh you know action part and you can
talk about kind of the same theorems
they can they they carry over and now
it's a matter of reinterpreting it of
course there's many other uh Downstream
consequences of that but at a high level
I think we've done most of the technical
conceptual work and now it's sort of
shoehorning in the the action part and
you can ask the same questions
right yeah um you can ask the same
questions but you don't get the same
answers ah
okay the active case is much more
complicated and and much more tricky I
mean we I mean apart from the base
optimal notion which is sort of an
optimal notion which is I would say Good
by definition or I mean from the
foundational um derivation of of of
probability in base um it's it's very
difficult to come up with Notions of
optimality in the agent case which are
on the one hand strong enough to be
convincing but on the other hand weak
enough so that real agents can actually
satisfy them so that that even the the
right notion of optimality is still
still open I would say unlike in the
prediction case where use regret or
redundancy and sort of um you know you
you don't have to compromise much there
anyway okay let's start with the agents
and um for a
moment for a second um let us forget
about solomonov and all these kinds of
stuff but start very simple let's assume
we know the world right what happens
what's happening okay so the setup is
the following I mean it's a typical
agent environment setup and you know
soon the rewards come in I draw the
picture a little bit different from the
standard way because um you know
standard Isis is usually you know MVP
based and um that is too limiting for
AGI agents right we want something at
least when we start uh something which
is you know General um that means
general history based environments and
policies and so the picture I usually
draw is you have an
agent
and you have an
envir an
environment and the interact with each
other um and the agent as well as the
environment they can remember stuff
arbitrary long in the past so let's sort
of put this sort of on a tape
yeah so there's a sequence of
perceptions so e are
perceptions that was the X before
the agent can have okay and um um once
it has a perception it can act
somehow is perception the same as
observation
no
okay you will see in a second okay okay
um so and
um the agent then acts
somehow and um and it you know this
action can depend on the whole history
of of perceptions up to time step three
and then the
environment gets and can remember all
the past actions of the agent um if it
wants to um and then produces a new
percept so that's the reason why it
connects to E4 that's the next time step
produce a new percept and then um the
cycle um continues so formally what we
have is we have an
agent which we call I mean the the the
the behavior of the agent is called a
policy right which takes and here in
this picture it looks like that the
agent um only depends on the on the on
the perceptions but the agent can also
remember its own actions I mean I don't
need to sort of because it produces the
actions because he knows its own actions
so the policy is a mapping of past
actions and
perceptions up to the star means sort of
1 two 3 four five and produces a new
action and uh the
environment um is also having access to
the whole history of acent perceptions
and the last action of the agent and
then comes with a new
perception and um since the policy and
environment can be stochastic you
know I just write this as a weekly error
weekly means it can be a stochastic
sort of you cross a two one something
like this okay so and this
interaction um produces an action
observation action perception sequence
so e t um is sampled from new of e given
and now I use this glue notation
AE a sometimes disappears here a is less
than T and the last action of the agent
a e so AE sort of glue together so
action one perception one action two
perception two up to T minus one and the
actions are sampled from the policy or
with theistic policy is just you know
ttic output action given the
action perception history right okay you
start at tal one there's no conditions
and you generate them sort of you know
based on the so this a this is AE uh two
like the all the pairs of AE up to less
than T right just to emphas just so so
the joint distribution so we can do so
if we take so we we start at tal one and
the first thing is the agent's action um
so it produces an action with a certain
probability so T is equal one so there's
no history it's just the first action
then the environment reacts to this
action
um and then you know T 2 starts tal 3 up
to say tal say assume the agent di times
that M so for Simplicity I just assume
that the agent has a very long Horizon M
say lives for 100 years and then dies
right so um but you can also do infinite
Horizon but then you need discounting
for the rewards and so on Infinities is
always a little bit annoying so I I I
keep it simple here so this is a joint
distribution which generates the action
perception sequence up to M and which we
by new P okay it maybe I should this off
E1 2 m so that's the probability of this
act perception e a a
e a e 1 2 m so that's the probability of
the action perception
sequence um if environment new if agent
Pi interacts with environment
new so now um we ask what does the agent
do right and we want it to do well with
respect to some Criterion and in
reinforcement D you have a reward signal
um so we split the perception into an
observation and a re
yeah so the perception
obss okay o 2
R2 and so on so when I write e it's
always with here um o r okay and the
goal of the agent should be to maximize
its total reward over its
lifetime up to M but these rewards are
you know are stochastic right you know I
mean definitely the environment I mean
you know either the environment is
itself stochastic or later they have a
belief over the environments so um this
happens this reward sequence happens
with a certain probability right and
what's the probability well the
probability is new PI right but the
policy Pi we want to choose right we
only care about the stochasticity of the
environment so the probability of
observing a certain perception sequence
given a certain action sequence
um actually let me I come to that later
let's keep it
simple so um this
produces um uh this reward sequence but
with some certain probability so let's
take the expectation so the expectations
respect to the environment new and with
respect to the policy Pi okay and this
expected reward
sum is called the value of agent high in
environment new sorry your I think your
RS and your news look similar that's an
expectation of rewards is that
right well yeah in in in the squares is
ours okay a new sory yeah your ARS news
okay all right I think you know what
they
have anyway okay anyways okay okay so so
that's the value of agent Pi in
environment new
okay so if we know the true environment
okay by the way and you're you're are
you absorbing the discount factor into
the rewards then h no discounting here
because it dies at Horizon M oh ah I see
okay yeah I I could do discounting and
then I can take the limit M to infinity
and all the EX and they're also more
useful so but I'm not doing that and
there's also you don't want geometric
discounting because for any gamma you
choose any gamma you choose corresponds
to effective Horizon which is one
divided by one minus gamma so if you
choose gamma 0.99 it corresponds to an
effective Horizon 100 but there are
problems which need larger Horizon if
you choose gamma
0.999 it's Horizon thousand but there
are problems with need Horizon but there
discount schemes which are not geometric
which generate agents with a growing
Horizon for instance proportional to the
age of the agent makes a lot of sense
right but I don't want to go into
this um okay so so if we know the true
environment then our true the agents Pi
true
expected um uh reward sum so the true
value is V Pi mu and well we want to
maximize this right so me me is the true
environment and new is the uh new some
environment some got it okay yes yes so
that it's easier to read
okay okay um okay and this let's call it
P start okay but um so that would be the
optimal policy right if we knew in which
mind we are
okay okay but well we don't know me so
what do we do yeah okay we learn me how
do we learn me as a
basan what what ban
updating yeah ban updating which means
if in the predictive formulation you
just replace it by the mixture distri
yeah yeah yeah exactly and then and then
as you make more observations you'll get
convergence exactly okay so now let's
define also Pi s Bas mixture um well the
ban mixture is pretty much obvious I
mean everything is now conditioned on
action so I mean I could write it down s
of um X1 to M um so E1 to M given
actions A1 to m is equal to well new
e E1 2 m given A1 um so there's some
suby this is not the real prob
conditional probability but I I I use a
double bar so here is sort of Remember
at the beginning I said there's a
difference between conditioning um and
indexing so that is actually indexing on
a and here it makes difference um so so
uh some people have spent a lot of time
and figuring out what is going on here I
mean in one sense it's trivial in
another sense it's really subtle what I
call them I call them chronological semi
measures say Chron probability
distributions which satisfy the
causality constraints um but again we
don't have to go into it it's it's in
some sense it is is obvious okay so now
um this P P that is what we want P but
we cannot it because we don't know so we
use this policy Pi starai okay which I
call
AI xai it's not the I model yet but we
are close Okay so and now we want to
compare the performance of this basan
agent to the agent which knows the world
okay so how can we do that well we look
at the value but this Cai value is just
sort of a a tool for creating a policy
this has no meaning right um I mean not
not not direct what we really receive is
the mo value okay so but we act with a
Cy optimal policy okay so we ask what is
the true mu expected reward th if we act
with aide policy and we compare this
to the
optimal mu agent
okay this optimal agent of of course has
smaller value than any other policy by
construction because it's just an
argument but what is this relation
between the base agent and uh the
optimal informed agent and well in the
predictive setting we proved um this
loss bound so soone of bound and um and
so on and in active
setting under certain extra conditions
you can also prove
asymptotically that they converge to
each other on average um you can prove
So-Cal self-optimizing results you can
prove um asymptotic optimality results
there's weak optimality strong
optimality optimality in Cesaro sense
there there's lots of different
optimality Notions and there but they
all come with conditions under which
this holds so they're not condition free
by I think you meant lower bound we're
trying to maximize reward here
right AR Max sorry
oh yes yeah so this is approximately
under in a certain sense under certain
conditions on M I mean for instance this
framework is General enough that if you
choose a class of environments M which
do not depend on the action so if I cut
this Arrow here from the action tape to
the environment so um so in the diagram
um so if the new respects this so it
does not depend on the action so here I
made an error if it does not depend on
the
actions then we are back in the passive
prediction setting and for instance for
this class of models right um we get the
solo one of bound de yeah but we get
also bounds Beyond this class of course
otherwise it would be
B um okay um so finally that is nice
but we have to choose a class and from
an AGI perspective right we want the
class to be I mean from a technical
perspective we want it to be as small as
possible to deal with it practically but
from an AI perspective want to big
enough so the true world is in the class
and I mean if you look at physical
theories standard model uh generativity
and whatever you know they're all sort
of computable theories I mean very hard
to compute but they're all computable so
again if you take the class of
computable probability distributions we
should be pretty safe that the true
world is in the class yeah so again so
we choose M to be
mu which is all
computable computable in this case lower
semi computable chronological semi
measures if you want to be precise yeah
but roughly speaking all computable
probability
you and as prior as before we choose two
to the minus theog complexity of
then you get aai which is th U and this
is called the
arim okay and now if you think even
intuitively about what this model does
it it combines Universal sequence
prediction which we have shown to be
optimal with optimal decision making in
known environments when also optimal and
combining this in these two ways by just
plugging solomonov into um into the
sequential decision lyric framework um
sounds
like an optimal decision maker in
arbitrary unknown worlds and if you sort
of if you parse the sentence this feels
like AGI and you can also Define an
intelligence measure out of this um so
you can regard
V Pi that is
the performance of policy Pi averaged
over all environment in the class with a
certain prior and you can call this for
instance intelligence of an agent pi and
P
leg my first PhD student and co-founder
of De mind wrote a whole PhD thesis just
about this intelligent measure so Supply
is a policy SI is this uh kagor of um
sorry the Solomon of um mixture prior
right and you're calling this value
function the intelligence uh yes
intelligence of agent Pi so Epsilon of
Pi um because I mean this is um this is
I mean we can write it out explicitly
linearity this is just the sum over all
values in all
environments over the
class oh I I see I see it's sort of like
measuring its Fitness with respect to
General environments is is that how to
interpret it okay yes so it measures the
the yeah the average fitness over these
environments average with with a sort of
what comes what comes prior I see let's
let's take this down to earth a little
bit because you know we we we're working
in the space the countable space of all
computable programs in practice right we
never do have this Infinite Space where
we have to uh juggle all these
quantities in practice there is some
finite subset of of discourse of
consideration and I'm wondering to what
ENT if you choose a large enough finite
set sort of this becomes uh let's say
applicable tractable uh meaningful
right um yeah but that is probably a
little bit too naive I mean sort of I
mean this finite set needs to be really
large right so assume you can describe
our universe in 100 bits right I mean
100 bits is not very much right so but
assume you can describe in 100 bits
right there are two to the power of 100
programs of up to 100 bits right
um so that is already a class of size
two to the power of 100 really help you
so unless unless you can do the mixture
more efficiently than knively like in
the CDW case I see I see yeah basically
as soon as computable but practically
not that's right that's right very large
finite numbers are are basically Out Of
Reach very quickly in this in this
business yeah yeah anyway um so that's
all good um let me briefly I mean that
looks very abstract let me give you um
uh another formulation of this agent
which is much easier to grasp what is
actually going on I mean here we're
doing Arc marks over policies and
policies are your functions from high
dimensional spaces there's a different
way to writing this B down um again um
avoiding all you know base and mixture
and all this kind of stuff let's first
again start with the true distribution
mu of E1 to M given action sequence and
again this is not really the conditional
distribution okay uh so that's just you
know the the the perception sequence
assuming that a certain sequence is done
okay so m is where the agent dies we
don't care about the last perception
that just um ah um what a second the
goal is of course to maximize reward
sum okay um but um the last perception
we don't care about so let's just take
take it out and what that means is
that
um that um we just take the expectation
um over the last perception so now we
have the last action and then the world
ends right or the age ends so what do we
want to do well we want the action to
maximize rewards so we take the action
well which maximizes this reward sum
okay so that's in the last so we we're
going from back right from the last last
day or last
uh uh second of the agent and um so now
where how did we get there well the
environment produced an perception em
minus
one at before we receive the agent
received the perception we don't know it
so let's take the expectation to e minus
one okay and now we take the
action at time M minus one which
maximizes the expected future what so
that is I mean you're for for those I
mean you're basically uh unrolling the
Bellman optimality condition right yes
yeah and the the bman equations are
really only useful if you have a mark of
process right because then you really
have this self-consistency but because
it's history based I mean you can write
it down in a belman form but it's sort
of it's it's not really recursive
because at every recursion step you have
a different length history so you don't
really gain yeah if this were the mdp
but you're you're basically un you're um
you're unrolling the tree right and
you're just working backwards yeah yeah
okay okay so and then of course we go up
to assume we are currently at time step
k um so we sum over the e k and we take
the maximum
at St k then the optimal X is just the
AR
Marx okay so um and you can write it
down in a tree right if you look look at
in the three
representation right I mean basically
you decide right once you decide what
the optimal move is at a node then every
then you can analyze the optimal move
from the parent because the parent you
right you you have the reward for each
action and then the the value of of the
of all the you know of the child which
ENC capules all the decisions below it
and so you just kind of recursively work
your way up right exactly and so if it
were a classical Mini Max game right um
You would maximize your value when you
have actions and the environment would
minimize the actions so then you would
have a Mini Max tree but here the
environment is not necessarily adversary
stochastic instead of a Mini Max tree
you have an expect Max tree right why
you have these expectations here right
right so the sums are the expectations
yeah okay so that is the
expected Max
three Okay so far so good this is if we
know the environment and by the way we
can specify on assume we play chess um
so we could Define an environment Mo
which is in this case deterministic
which is adversarial which means it
would only put probability on one
particular from the environment's
perspective action from the agent
perspective observation namely the
optimal action then all these sums would
collapse to picking out the minimizing
element and the expect the max reduce to
min
max so if mu is the chess environment
with a optimal opponent then this would
reduce to Minimax so it's I just want to
say it includes also Minx of brail ah
right because I think what you're saying
is that if you play against the
strongest possible opponent there's no
margin for error so they're always going
to choose the the thing which which is
minimizes your reward which maximizes
the adversaries reward so everything
concentrates on on the best moves and
comes yeah that's right mhm okay so so
far so good but that's with respect to
the true environment right um what if we
don't know the truth okay now the
pattern repeats what do we
do we
replace yeah yeah yeah so I could just
write
here and we would be done but let's be a
little bit more explicit so remember in
the prediction case there were two
formulations of thisai one was in terms
of Bas mixtures and the other one was
just piping random noise through a
universal touring machine which was you
know much easier in a certain sense but
we can do the same here nothing much
changes so um we look for programs P
which
output
um um
perceptions E1 to M but now
um uh need some space it also we have
actions as conditions right so the
universal touring machine also has the
actions available okay and we look for a
program which given the actions of the
agent and um uh produces the the
observation sequence or explains the
observation sequence relative to what
the agent has done okay so and we weigh
each program by its probability and you
know the probability of a program should
be one half to the L number of bits so
we weigh each program at two to the
minus L of p and then there are many
programs which output this observation
sequence so we sum over them so in in
this formulation you look for all
deterministic World models
P which are consistent with the
observations E1 to M but of Al it also
depends what the agent does right if I
look left
left then I see the perception is
different than if I look right so
everything is dependent on the actions
that's the reason why the action also
function you and sorry was there a
reason we went back to the deterministic
case that I assume this all works in the
to write it down explicitly I mean can
write Cai and then we can look up Cai
and so on but now what we have here if I
Circle this
here apart from the definition of a
universal touring machine which is sort
of you know not trivial right everything
is completely explicitly in here there's
nothing okay there's an action space
site and observation space site which we
have specify but otherwise everything is
here written down explicitly nothing is
hidden I mean that's the only reason to
write it out like this I mean you know
you how do how do you enumerate all
computable probability distributions yes
you can enumerate all functions and then
you can know Top This functions towards
the pro so I mean there's a long process
to really get to this basan mixture
distribution but here this is Trivial
right so you just write it down in you
know 20 characters that's the only
reason it's equivalent I can just by Sor
okay sure sure sure sure sure sure
sure okay so so that's
this II agent
and um I guess we can move on from this
I would like to uh talk about some
variations of this model um which has
advantages the disadvantage so given
that it's very hard to prove convergence
results um Alternatives have been
developed okay so let's go back to the
original formulation where we had um
um where we
took let's maybe this formulation we had
the the S value one representation what
represent is a new
value um times its
prior and then some overall new in the
class so that was
the th
value and
um and then we ar maxed it to get the
optimal policy okay right so here we
look for the
performance to maximize the performance
average of the
environment what we could also try to do
we could do a Mini Max instead of this
we
could do the minimum over all
new maybe still waited right over
new um and then AR marks it
see the first line is just linear
linearity of expectation right the first
line is linear expectations yes yeah
okay so if you replace the sum by um by
a minimum with or without this weight um
that would be trying to perform best in
the worst possible worlds right we look
for the new which gives me Minal value
and I want to perform well in this
that would be sort of a mini strategy
okay interestingly if you have
prediction problems that can work under
certain circumstances well usually of
finite classes or compact classes and so
on but for the active agent case that is
actually a bad
idea very
interestingly
if you
replace the minimum by a maximum so it's
a maxim Max principle so you look for
the best possible world and want to act
well
there you can show that at least for
finite
classes you get an ASM totically optimal
agent and then you can extend it to
countable classes with some tricks of
making the class growing you can extend
it
to um um you can extend it to um compact
classes I mean compact classes always
you fill it with fin Epsilon balls then
you can extend it to separable glasses
this result so anyway so this is I mean
this is saying like you should be under
these assumptions you should be an
optimist not a pessimist right you act
as though the world is
uh uh in your favor and and if you try
to optimize that situation you'll do the
best versus the other way around where
I'm going to act in a way such that I
assume the world is not is most against
my favor right yes and you can explain
it in two ways so we know as soon as we
go to the active setting we need
exploration and being optimistic
encourages exploration so if if there is
an environment um where we you know look
this is all still Bas so we don't know
much about it so if you believe it could
be good right then try it and either it
is good then it was a good action or not
good then we have learned a lesson and
then based on the posterior it will go
down so um that so the the the optimism
gives you
expiration
okay was there something else uh is the
optimistic agent the optimistic you said
there were two things right optimism is
exploration was there something else ah
so um it encourages exploration and well
I I and also I mean if you are
optimistic and then you
act which I said either you were right
then everything is good or you were not
right then you learned a lesson and
this this is a bit of a philosophical
tangent but I think where
this makes a sharp contrast with reality
is that you know uh two things
one we as uh mortal human beings uh
positive and negative rewards are highly
asymmetric right death is like a
negative infinite reward and in some
sense positive reward is bounded because
there's it's only so much you know money
or you know diminishing returns right
and then in practice people are do have
a uh you know concave reward uh utility
function for precisely that reason right
we're much more risk averse and and and
so we're we're usually more pessimistic
in some sense than optimistic um anyways
maybe this is too much of a
philosophical tangent but just something
thing that uh why aren't we more
optimistic because I think our our
situation differs from the assumptions
of of whatever this agent is by what I
here that the rewards are bounded in the
interval 01 or at least of in a bounded
interval you I mean in my old book I
have a a whole section about how to deal
with uh uh concave loss functions and
how to reduce this and so on yeah I mean
could better a whole sure sure
okay do that of course of course I just
yeah so and also I mean this is not um
um uh knife optimism I mean you have to
update with the posterior right it is
sort of it is a it is a
um uh a
realist optim yeah yeah yes that's right
because you take the feedback into
account
right environment which we in consistent
with what you were hoping for that's
right yeah that's right okay I mean in a
very tiny setting you know the UCB
algorithm you know upper confidence
Bound for bandage problems
right that's a similar I mean similar
right you optimistic with the arms and
either you were right or not then you
learn something and then I mean you you
still respect your posterior belief um
in the environments okay so that was the
optimistic agent um another agent is
Thompson samping agent for which um that
is one agent for which you can actually
prove um with um out um any real
restrictions um uh asymptotic optimality
at least some form of asymptotic
optimality and what you will there is so
now I mean I said okay so to summarize
we took the ideas from part one about
Universal prediction added in
action
and and the optimality conditions now
become optimality um conditions on
things like regret and learning the
environment what you just outlined here
were sort of um sorry let me start uh
before I jump to that and and and you
could even furthermore write an explicit
formula for what uh a is um these
variants that you wrote down were sort
of different ways of trying to uh learn
the environment by using other sort of
uh strategies let's say learning the
learning of the environment was the same
the learning is always a base rule okay
how to choose the actions was a little
bit different sorry the base optimal
action the Thompson sampling choose as
well the Thompson sampling action and um
then the knowledge agent sort of is
exactly I but ches the reward function
for
you I mean they're different yeah I
guess they're these are like kind of
different uh policy learning methods
essentially is that a way of phrasing
it yes I mean Thomson something and and
and I see sort of his different base
of follow follow follows different you
know you have to distinguish between
updating the posterior belief mhm and
what you do with this belief right how
to act according this belief right sure
and so toming and I are sort of
different choices uh and the knowledge
seeking agent solves a different problem
namely where do the rewards come from
and self a tries to avoid the
expected okay okay anyways okay so I
think um maybe okay let's just let's
just leave it at that as as the the
summary
um so I guess we have time uh some time
maybe just to uh
say just a few odd odd things here and
there as as we choose I know you wanted
to talk about the grain of Truth problem
maybe that's just one last thing we
could put in maybe close with some
philosophical discussions I mean we we
already had a few but maybe anything uh
that you'd like to um you know kind of
like final thoughts about about the
subject essentially yeah yeah yeah okay
that's true that's the the multi-agent
setting yes um so far we have only
considered one agent but since the
framework was so General that the
environment could be anything there
could be of course other agents too yeah
but there is more to say than this okay
but let's first draw a picture um but I
don't need to say too much of it um it's
extremely
sophisticated um the the the final
result what I but I want to present the
grain of tooth problem was a problem
which was open for 25 years and then
some of my students uh solved this so
you have now multiple agents which e
have their own policy so they assume
have K agents K
agents and the policies you know Pi 1 up
to Pi K and they act with an environment
now so there's an index up there so the
agent one acts with at1 at time T and
then perceives
et1 um up to the last agents so APK and
perception is e TK so a pretty natural
and of course it also goes in Cycles
okay
so what we could do is we could just
look at the first
agent and regard all this here right as
an environment right this first agent it
acts and it perceives and that this
environment itself sort of consists of K
minus one extra agents we can ignore
that to some extent right so let's call
This Cloud M by the way are the agents
always acting in succession you know
cyclic order always or or is that is
that an irrelevant detail um that's
irrelevant
for okay okay um I mean technically it
becomes important but but for here it
doesn't matter they parallel okay like
like you in Game Theory parallel actions
so on but let's not go into this okay
okay so um so let's start I start a
little bit different before we looked at
I didn't never specify the policy class
because we just looked at all policies
and then the best among all policies so
let's start with some policy class
P
okay some potentially restricted class
okay and um let's also assume that um
all these
agents you know have some policy in the
policy class not necessarily the same
policy and
so once we have given the policy class
and assume there's also an environment
class Sigma but let's assume that's just
one environment doesn't really matter
right there also a class of environment
Sigma um we can construct then by you
know gluing this K minus one agents to
this environment Sigma and can create an
know a traditional One agent environment
out of it okay and we do that for all
possible combinations of policies in
this policy class and this generates a
class let's call this m capital Pi maybe
I should make a double bar so you see
that's a capital Pi so that's this
class M Ty okay so here we start with
policies and create our single agent
environment class
miy now we have
miy the next thing is we construct our
the base mixture over this class as
before and now it is called the
aai again it's invisible M index Pi okay
gets a lot of lots of indices
okay now we have the base mixture
distribution the next thing we want
to uh construct optimal policy with
respect to this Bas mixture like like
the I model
okay this just to get this straight so
you're trying to reduce this for uh
multi-agent formalism to the pre
previous formalism where there was a
single agent so it almost sounds like to
do that you need agent one to act
alternatingly with the other agents
right so it's sort of like action and
and pre percepts right is that is that
an
assumption the action and the perception
is not is alternating but all the
actions are
parallel okay anyway go I can spend at
least 50 hours on this if you want okay
okay but okay let's let's continue okay
um so now we look at the value of a
policy so of policy Pi Pi yeah Pi one I
should call it right in this basan
mixture over this class we have just
constructed okay and what we want is
well we want the optimal agents so we
take the AR
Max and that is our PI one
star so so hold on let's see let me let
me think about this um I see I see so mi
is is the is the universe of policies
we're going to consider um the C is the
the uh the whatever the salt yeah what
do you call it now the salomo mixture
the a XC mixture what what's the name of
this mixture Mi I sure but but you are
using the oh it's any base mixture but I
thought you using the I'm not using any
specific Solomon of Cl Sol oh I see it's
any base okay sorry okay c c is a
general base mixure okay that's what I
was trying to understand okay I see okay
okay please continue yeah yeah so so
index
M always means the mixture with respect
to the class m whatever m is Yeah well
yeah right I see well I see m is the the
set and also the weights then I guess
yeah okay yeah okay okay okay okay so so
we go from a class of policies to a
class for a single agent environment
then we construct the base mixture and
then we construct the optimal policy
with respect to this bace
Mi okay so now so far all good but now
comes the real
question you know we started with a
class of policies and why this Loop we
constructed a new policy Pi one star but
is this policy actually in the class or
not
if it is not in the
class then it would mean that if we want
these agents to be based optimal agents
then they are not in the
class but we started out with a class
assuming that these policies are in the
class so we have a problem so what we
need is we need K one star to be in the
class by itself sorry what's the what is
the obstacle because if if something if
you're considering the class of all
whatever computable semi computable blah
blah blah well how could it not be you
want a smaller class is that is that
what it is if you start with a class of
semic
computable uh distributions then the Cai
is also semic computable but the policy
Pai is not lower semic computable
anymore it is only limit computable so
it is one step further removed from
computability
ah I see sorry I see we didn't sorry in
the previous in the previous setup with
uh with that was not multi-agent I guess
we didn't care where piar lived now we
do okay okay yeah okay so that's and
that is called the grain of Truth
problem grain of Truth
and sorry can you explain the the the
the the naming of that um I guess it
comes from um you the true environment
in the class um and um but you know it
needs to be it can be a very big class
and just you know one environment needs
to be TR it needs to be in there this is
the grain of Truth okay okay okay sorry
please continue yeah so and uh that was
by uh by carai and car and Bala um 993
or so um so they formulated this problem
and maybe in this paper in in in in
another paper um they or somebody
constructed a a tiny tiny super boring
class where this gr of Truth is true I
mean it's more or less sort of a
environment um where you have a fixed
action and then you die or something
like this I can't remember I mean it's
definitely not AGI is not even a banded
nobody else could ever find any
class non- trial class where this grain
of Truth holds and so that was this big
open problem and and um one of my
students Yan like and some me guys
actually before that they found a class
which is relatively so the the M guys
constructed a class which it was not
even sure whether the distributions in
this class are in the arithmetic
hierarchy so this is something I mean
really crazy I mean of you
um again just leave it like this but Yan
like then showed it that it's in Delta 2
so it's limit computable which is sort
of the realm where solomonov Works
anyway so this class is not the class of
lower semi computable semi distributions
but it's a class of all reflective
Oracle computable measures um and this
construction is Hell okay let's not go
into this so we have as a
result we have a class
M which
contains all computable
distribution such that pi1 star is in pi
so contains so
contains contains a grain of
truth but the important thing is it
contains the computable ones which we
want and the another important thing is
not too big it is at
least a subset of Delta to Z it's not
not so
crazy which is really great
because the reason why we care about to
be this put in the class that means the
condition that s is in the class is now
satisfied yes so um so the the the Cai
is itself in the model CL or the P side
more precisely than the mod class
itself therefore the conditions
um which you usually need for most of
the basian theorems the basan most of
theor if the true class is in the model
then good things will happen right and
so this condition is now
satisfied um and we can apply the
previous theorem and especially the one
for the Thompson sampling agent if you
now do Thompson sampling in this
multi-agent setting we get an
asymptotically optimal agent which in
this case means they converge uh to NES
equilibria um in this Ultra general you
know model class um which is which is I
mean from a theoretical perspective it's
a highlight of also the book then um um
this result
H okay wow I think there's a lot to
unpack here but uh I think you know at
this point only the experts are here I
think uh we could end with just two more
things I I did say philosophical
discussions but maybe another important
topic maybe if you could just say a
little bit about it our computable
approximations because everything we've
done now it's sort of very abstract and
maybe oh how would you modify this for
for real
life yeah so actually it's sort of I
mean to the extent that we have done it
um it
is easy to explain so the first
approximation we did is we just used for
M the class of uh marov environments
uh actually K order Mark of environments
uh was it K
order yes I think K micro environments
and for the K mro environments uh you
can easily I mean the the mixture over
the parameters Teta gives you you know
KT estimators and then for if we used
only binary actions observation spaces
and then the expect max if it's binary
tree you can roll it out to death eight
which means 16 to to the 16 sort of
these days of much more and then we
considered um the small 2 by2 Matrix
games like pris dilemma t for T playing
against trial strategies random
strategies um against uh uh t for T um
sorry that they games like prisoners
dilemma and matching pennies and battle
of the sexes and stack hunt and and the
chicken and so on so there five sort of
standard games um and and did some
experiments and the outcome was more or
less like you know
expected um I mean these are
approximations so if you play one
stronger approximation against the
weaker one you know the stronger one
wins um sometimes they cooperate against
sufficiently simple strategies like TI
for T if it's too complicated they don't
cooperate so um so more or less sort of
um it worked as expected next uh more
complicated
approximation was then using the ctw
remember sorry let's here sorry so so
now the the the a setup worked for
General computable environments a
computable approximation is when you say
h sorry sorry let's let's back up
there's the true environment and then
there's the class of environments you're
going to use to approximate the true
environment and and and U mu might not
be in M of course that's going to be
most of real life right and so you're
seeing how well can you do in in this
sort of misspecified setting right yes I
mean if if for instance uh we let I play
against TI for Ted TI for Ted is a one
mark of strategy which is in the class
right then the theory should hold but if
you play against you know more
complicated environment especially if we
play against itself right then we are
outside of the class Theory breaks down
and we have to just see empirically um
what
happens although let me try to think if
uh how do I say
what I want to say is uh oh oh I see you
only have a you only have a u right a
binary alph or some fixed alphabet okay
I was going to say like I mean I guess
like very small alphabet
yeah yeah otherwise if you if you
allowed unbounded alphabet then I guess
you could include board games where you
have very a very large State space of
possible boards but but obviously with
binary you you're not in that situation
yeah yeah yeah okay anyways
yeah okay so that was the first very
simple
approximation um
then the
MCC ctw there what we did there
is uh we use this CDW distribution right
which is much more powerful um but still
very fast to compute but now for
uh larger either observation action
sequences or for non-binary um you
cannot just do the expected Max Brute
Force um but um there's an algorithm
called monteal
research um which we just adapted to our
case and uh we deployed it to um which
ASM totically for enough samples
converge still to the exact um expect
Max um but of course I mean you know in
practice you never close but you know
this is nice to have an algorithm which
at least anytime algorithm is running
long enough sort of you you get to the
truth so it still has you know also this
theoretical guarantees in the certain
limits and we applied it to a lot of um
toy problems like grid worlds um and um
the most sophisticated a very trivial
form of Poker called poker um then
and then we ran it on um on
Pac-Man um well we call it pokman
partial observable Pacman um and um for
all the toy worlds including K poker um
this approximation learned to um um uh
play optimally asymptotically and for
for Pacman we also saw performance
improvements but I mean of course it
didn't converge to Optimal a more
sophisticated approximation for these
situations what's
the I mean the observation is whatever
like like like in Pac-Man it's the it's
the screen right there some some some
end byend but we do hman um where the
agent only observed um in the four
directions um I can't remember exactly
anywhere whether it was up until a wall
and then or up
until uh some object or ghost or
something was there and then the
distance or or maybe just one cell so it
was it was from a first person's
perspective what um the agent can
see which made the observation space
smaller um so it was more easier to
handle in this case you know remember
that was way before uh uh the Atari
paper from I see mind and by the way
that was by this approximate by Joel
veness who then also you know work on
the satari problem so it you know
evolved from from MCI CDW playing Pacman
toward
thear okay okay
okay great so okay so is that um um let
us um briefly talk about the uh llms
right so I showed you the connection
before um how these llms trained on log
loss are essentially trying to
approximate solo you know right but
that's the prediction part how is up the
action part okay okay if you look at the
action part um well I mean people use um
um um Foundation models um also for
agents and maybe the closest would be
muzero right um where you take a learned
model and then do planning on top of it
so instead of approximating solono by
CDW you could just approximate it by a
large language model and then do
multical research on top of it um there
are other ways like you know there's
Chain of Thought and there's tree of
thought where you know you roll out it's
a little bit simp to MCTS right you roll
out various uh Futures and then you get
a tree right and and then then you
decide what to do so um so that would be
a way
to
um to find a connection right and sort
of muzero is in a sense close it does
the monal research which approximates
expect Max and it uses uh well muz
doesn't use a language model but uses
other models so if you would use a
language model and then with mu sty
planning then you could regard this you
know as a rather straightforward I mean
not straightforward you know but rather
um uh principled way of approximating
the I model so I'm in the language model
setting what would be the
reward ah you would um also have as
tokens
rewards there would be some tokens which
are sort of related to reward I mean if
it's discret it's just a reward zero to
10 or something like
this oh you sorry uh I mean you know
with like things like rlf you know you
can you can uh have human Raiders give a
feedback as to whether yeah I'm not
talking rlf is sort of barely RL right
now what you would here have is that the
language model
itself so you you train maybe should I
shouldn't call it language model but you
know sequence model or Foundation model
or whatever so you you are training the
model of sequential data which consists
of actions observations and rewards oh
oh okay I see okay and then it also
predicts the observations and rewards
and then you just roll it out into the
future and select a roll out where where
the rewards are high right I'm a little
confused here
what what uh what's the problem you're
trying to
solve I'm trying to extend the
current rather simplistic approximations
of iy to larger model classes and um the
model classes we now know and the best
most predictors we have are currently
large language models oh I see got it
okay okay that makes sense that makes
sense you plug into
a instead of solomonov you plug in a
language model that's right then you
still have the EXP expect IM Max but
this you replace by m res like your your
your your your s your c is now your your
llm essentially yeah exactly okay got it
okay okay makes sense sorry yeah okay
yeah I was confused with the notion
reward thinking of R chff okay just okay
um okay I think we mc mc
I
llm so many it's like this almost looks
like all uh with the exception of maybe
the a it's all Roman Roman letters okay
it's like a bunch of Roman Roman numer
like you're like you're trying to write
a large Roman numeral or something like
that except except for the a the a
throws it away I don't know what number
that is if you threw away the a but okay
okay
anyways um too many capital letters um
okay maybe uh one final thing as we
close up I know there's a final chapter
or two in your book about philosophical
aspects book is quite philosophical in
the sense that it's not just all even
though there is a lot of math it ties it
wherever there's relevant philosophy you
you'll sort of make that correspondence
but um you mentioned kind of at the
beginning some historical context for
the prom of induction you know famously
Hume and his predecessors have sort of
um let's say I don't know how to the
right way to say it but but kind of cast
doubt about the validity of induction um
and then there's you know more more
recent works like the poer Miller
theorem about maybe various problems
with the formalism of induction to what
extent do those
perspectives uh are
they do they inform XC or the other way
around what's the relationship between
these well as far as I can tell and
remember solomonov was influenced by
car's theory of induction so car's
induction Theory and the carab the was
essentially you know maybe he did more
but was entially llas rule um and um but
laas rule has the problem that it cannot
confirm Universal hypothesis so if you
ask what is the probability of the next
bit being W given history you seem to
get a reasonable answer but if you ask
what is the probability that all future
will be W like you know you have seen
100 black Ravens right what is the
either the probability that all future
Ravens are black or that the hypothesis
all Ravens are black is true if you
solve that in the simple Bas La plus
model you get probability zero I mean
you don't even get prob you get zero
which makes no sense right so you see a
billion Ravens black Ravens and then it
predicts the probability that all Ravens
are black is zero right so so this model
fails and um interestingly I mean at
least from the technical literature I'm
aware of most quantitative approaches
fail on um on this uh task of
quantifying or predicting So-Cal
Universal hypothesis or Quantified
hypothesis and um although solomonov
doesn't explicitly sort of consider this
problem I mean I considered it later
solves this problem um so and um in in
one of my papers the
philosophical tretis of universal
induction I go through you know a couple
of these philosophical questions and
show how solom solves them there's a
problem of um of of zero priors there is
there is a more technical problem of
reparametrization invariance so there's
so this paper looks at a bunch of
philosophical and statistical problems
which
most approaches have and shows that
solves all of them okay actually in this
very specific case I think what you're
saying is the following suppose uh the
observations you made are all ones
you've seen a billion ones now there is
a there is a program which says actually
my program is print all ones and because
it has positive weight on that quite
large weight because that's a very
simple program then there is a positive
probability that indeed all future
digits will be one right exactly yeah
it's it simple as this right um it is
the th right and but interestingly uh uh
laas rule carab Theory and most of the
other the I'm aware of get it wrong I
see although although maybe it's a
little unfair Fair because with lassus
rule you're you're only allowed these
beri predictors and you're you're you're
in such a small model class that that
maybe you you um I mean of course
technically you do have P equals 1 as a
limiting point in your in your
hypothesis class is that you you never
you never select for it because you
always have to have some margin of of um
uncertainty right I I'm not even asking
for selecting that Pete goes to one I
mean of course ultimately we want that
if we see n ones and N tends to Infinity
the probability of this hypothesis
should go to one but I'm just asking
that it's not zero exactly that's right
that's right yeah that's right even this
most models get
wrong okay
um I don't know enough about theed
that's the prediction part and from the
philosophical perspective um from the
from the decision theoretic perspective
I mean there is you know something like
causal decision VI itial decision
there's also some philosophical
paradoxes and you know the newcomes
Paradox and you you
can you can try to you know reason how I
would sort of uh deal with these
paradoxes I think these paradoxes are
are very fun um but they are rather
irrelevant from a say practical AGI
perspective because I mean that's
not you don't face this new come time
problem in practice right because there
is no omnis person who can predict what
you're doing and put it into and and if
so you have the differential problem and
so on I discussed that a little bit in
in one of my papers um but so I would
think the the Deep philosophical aspects
are in the induction and prediction part
the exential decision part is sort of
relative okay I see okay okay anyways
okay I think we've definitely covered a
lot uh thank you so much uh for your
time Marcus this is a very fascinating
subject and I think um yeah hopefully
this will bring it to the attention of
more people