Latest / Strachey Lectures / Strachey Lecture: From classical to non-classical stochastic shortest path problems

Transcript

Strachey Lecture: From classical to non-classical stochastic shortest path problems · Strachey Lectures

• 0:02
  They. Okay, Welcome, everybody to the strategy lecture.
• 0:19
  So this is our distinguished only lecture, which is named for Christopher Straight G,
• 0:24
  who founded the programming research Group here and was one of the leading figures in the early history of computing.
• 0:31
  Before I introduce our amazing speaker, I want to thank our sponsors, Oxford Asset Management,
• 0:37
  to spend generously supporting this hearing since 2015, and they enabled us to bring a great future here.
• 0:47
  I think some of you have done some things that researchers and speakers want to meet them afterwards, and that's okay.
• 0:56
  So it's a great pleasure to introduce Chris Buyer and Chris on super well known for her work in verification.
• 1:03
  And actually, Crystal is also very modest because the biography she gave me omitted all sorts of things.
• 1:09
  But luckily for me I used Google and discovered Discover for myself.
• 1:13
  So I discovered, for example, that for her textbook,
• 1:16
  the principles of model checking has been cited more than 8000 times and is essentially the book in model checking.
• 1:24
  And she also has some very, very influential papers, including a work called Model checking algorithms for continuous time Markov chains,
• 1:33
  which again has really very, very many citations and introduces both the new logic and new model checking algorithms.
• 1:42
  Crystal is the author of the verification column in ACM SIGGRAPH News and has a bunch of honours,
• 1:49
  including Academy Award Europa and two honorary doctorate from Orkin, and she's really active in supporting German computer science.
• 2:00
  So I found Crystal on just about every German computer science committee that exists.
• 2:06
  She's here today talking to us. The title of the talk is From Classical to Non-Classical is to cast the shortest path and welcome Crystal.
• 2:16
  But this letter. Yes, like that. Yeah.
• 2:20
  Thank you. That's the Mike Rook. It does. It does. Okay.
• 2:23
  Yes. Thank you very much for inviting me. Thank you very much for organising this event.
• 2:28
  Thank you very much for sponsoring here.
• 2:32
  It's a great honour for me to give this presentation.
• 2:35
  Well I choose to a topic which has a long history.
• 2:39
  So. So indeed, first research was done 60 years ago, but in the end,
• 2:45
  for this non-classical versions of the shortest path problem then than it, it's more more recent work.
• 2:52
  And before starting with the technical things, I would also like to say it is almost 30 years ago that I visited.
• 3:01
  We had Kostka in Birmingham. We just were thinking which year it was 95 or 96 and this was for me,
• 3:09
  it was time to get in touch with with questions concerning the verification of probabilistic programs or probabilistic systems.
• 3:19
  And at this time, I also read these old papers about the classical stochastic sort of path problem, and I would have never thought that.
• 3:29
  So two years later I will give you a talk about this topic.
• 3:32
  So I would have expected that all the problems have been solved.
• 3:37
  Uh, yeah. So what is the question of oops of the classical tortoise past problem?
• 3:45
  So more or less the task is to construct a strategy or policy for traversing a graph,
• 3:52
  the probabilities attached such that the expected accumulated costs until reaching a target is minimal,
• 4:00
  so that the main problem is to minimise the expected costs or waits.
• 4:06
  A motivation. So this is a map.
• 4:12
  Here is Grayson, where I live here in Oxford.
• 4:15
  And going from Grayson to Oxford. Well, there are many possibilities.
• 4:20
  Taking a car, taking a train, taking a flight.
• 4:24
  Then there are no direct flights. This is an extremely small airport that we have in Grayson.
• 4:29
  Then I have to change in Frankfurt or Munich or in Berlin or whatever.
• 4:33
  And there is a lot of decisions that have to be made and there's a lot of uncertainty.
• 4:39
  So the flight might be delayed or the flight might be cancelled, which is indeed the case with my back.
• 4:45
  But flight have been cancelled. And so it's all finding one way shortest in the sense of shortest time for me in expectation.
• 4:57
  So this is one instance of the shortest path problem.
• 5:01
  Now, indeed, in different communities, a I planning robotics, operations research, this is a very classical and fundamental problem,
• 5:11
  but also for the verification of randomised systems or distributed randomised algorithms.
• 5:20
  Then for instance, one might ask what is the expectation, the time to termination, the maximal or minimal time to fall for,
• 5:30
  for termination or expected costs, the maximal cost that can happen in the worst case.
• 5:38
  But now that the formalisation of oops, the formalisation of these problems is using Markov decision processes,
• 5:47
  Now, I do not want to bother you with complicated definitions,
• 5:51
  which is not that complicated in that case, and the way the simplest way to explain them, at least I find, is to to do the following.
• 6:01
  We start with the classical transition system here shown on the left, where in every state there is a choice between different actions.
• 6:10
  And in this context, we consider the choice of different actions as a non deterministic choice,
• 6:16
  so different than for finite automaton where we expect to have the same label for a non deterministic choice.
• 6:24
  Yet the choice between alpha and beta is considered to be non deterministic.
• 6:29
  The other extreme is a Markov train where we do not have non determinism at all.
• 6:34
  Instead, for every state we have a distribution for the successful states.
• 6:39
  And Markov decision process is somehow the mixture of both.
• 6:42
  So for every state, we have a set of action, and for each we have a distribution for the successful states.
• 6:50
  I thought, Ah, this is missing because of this one.
• 6:54
  Maybe. Uh, yeah.
• 7:05
  So it was auto fault for Alfa. We have the distribution one for three force.
• 7:08
  And likewise we have, we have distribution for the beta and now in state f we,
• 7:13
  that choice between the different actions is considered to be a non deterministic one.
• 7:18
  And having chosen the action in a state, then we have a probabilistic choice,
• 7:23
  which is you to be an internal decision which which is indeed the successor.
• 7:29
  Now to talk about probabilities or expectations in Markov decision processes,
• 7:35
  we need some inference which resolves the non determinism, and this is what we call calculus or policies or strategies.
• 7:42
  So they take the history, what has happened. So the sequence of states and actions that have been taken in the past and then for the current state,
• 7:52
  they choose one of their actions, possibly in a randomised way.
• 7:56
  And doing this then you can, given such a catalogue, you can unfold the behaviour of that scapula into a tree like Markov chain,
• 8:06
  and that we have the full machinery to reason about probabilities and expectations.
• 8:12
  If you are not familiar with that trust, use your intuition.
• 8:15
  I think this would be enough for this talk. And what is this?
• 8:21
  The shortest path problem we deal with waits, integer waits that are attached to the state action path.
• 8:30
  So now here is the definition. The only important thing is that throughout this talk I've been saying MGP, I always mean a finite state.
• 8:40
  MGP only have finally many states and finite many actions.
• 8:46
  No. And as schedule can be formalised as a partial or it's a function from finite passes to distributions over elections.
• 8:55
  This would be the randomised case, and the deterministic case is where these distributions of direct distributions,
• 9:04
  which means that a single action is chosen as probability, one is chosen deterministically unique electron.
• 9:13
  And another important notion is that of a memory less controller.
• 9:17
  They do not look for the full history, they just look for the current state.
• 9:21
  And whenever I visit the same state multiple times, I make the same decision.
• 9:26
  This is meant by memory loss and on the following slides I often use the short form
• 9:32
  notations named for memory less deterministic and often more or less randomised.
• 9:39
  And another important concept that has been introduced by Luca and Alcohol more than 20 years ago is the notion of an end component,
• 9:51
  which, to say an easy word, is a strongly connected MVP.
• 9:56
  And by saying Sup MGP, what we do is the following For every state we have a set of actions that can be taken.
• 10:03
  And now we take just a subset of these actions. And this gives you MGP.
• 10:09
  The probabilistic choices for these selected actions remain the same.
• 10:13
  They remain unchanged. So if you look for the underlying draft, then it's indeed a sup graph.
• 10:19
  And for this being an end component, then this graph needs to be strongly connected.
• 10:26
  And there is one theory that has been established by a look at how he sees this 97 and also in multiple papers,
• 10:36
  what I call the fundamental property, which is somehow the MVP honour.
• 10:42
  Look to the fact that in a finite state, Markoff trains.
• 10:46
  We know that almost surely so with probability one a bottom strongly connected component will be reached and the system will stay there forever.
• 10:56
  And the MVP on a loop uses these end components state state that no matter which catalogue you choose,
• 11:04
  then the limit of almost all infinite passes will constitute an end component and tier by the limit.
• 11:10
  The meaning. If we look for the state action pass that occurs infinitely often.
• 11:17
  Now, here's an example. If you have an M.D. P Uh, and we have.
• 11:28
  It stopped working. Does it work here?
• 11:33
  Yeah. We have two end components.
• 11:37
  Does this still work? Yeah, we have to end components and we have this state here.
• 11:46
  Oh, that's great. Uh, but.
• 11:50
  But this one for what? This one here is a trap, states a terminal state where no action can be taken.
• 11:59
  And then lemme apply to such MVP's that my train of thought trap states means that under each schedule,
• 12:08
  almost all maximal passes for either finite passes that end in a trap or the infinite ones.
• 12:16
  They indeed end either in a trap or they eventually realise an end component.
• 12:21
  And by realising an end component I mean that the state should pass the infinite loop of constitute an end component.
• 12:31
  And for the special case where we do not have to.
• 12:35
  Okay, but we do not have any components at all.
• 12:41
  So an easy free MGP then allows Lemma simply states that with probability one,
• 12:48
  no matter which catalogue we choose, the system will end in a in a trap state.
• 12:55
  So now the typical task of synthesis problems for MEPs or formalise the synthesis problems would be given such
• 13:06
  a finite state MEP Find a scheduler that's maximises or minimises the expectation of some random variable.
• 13:16
  So and the input of this random variable are simply maximal parcels.
• 13:21
  So one very popular measure is the discounted rate.
• 13:26
  Remind that you have these individual rates for the for the state can pass and now this discounted rate of a maximal pass.
• 13:35
  We take the sum of all positions in that path.
• 13:40
  We take the rate which is collected for this with the corresponding state action alpha.
• 13:48
  And we multiply it with the ice power for discount factor or gamma, and it comes from value strictly between zero and one.
• 13:57
  And with government being strictly between zero and one, then we do not have convergence problems.
• 14:03
  Even if the sum is infinite. Total waits is more or less the same, but you can think of it with discount factor one without any discount tractor.
• 14:16
  Now if indeed convergence is an issue for infinite passes.
• 14:22
  And I would say it is not that interesting with the total wait for infinite passes.
• 14:28
  Without any further outside constraint.
• 14:31
  What has been done in the literature is either to consider only finite passes, either in a finite horizon setting,
• 14:40
  which means that we have some fixed bound for the length of the passes that we consider.
• 14:45
  And then we look for the maximal expectation of exactly and steps or the infinite horizon case where
• 14:52
  we have a distinguished gold state and we only accumulate the weight until we reached this goal state.
• 15:01
  And with the site assumption that we only look for those catalogues that indeed reached this goal, state with probability one.
• 15:09
  These are the so-called proper catalogues. And there is another very prominent measure it random variable which is used in the literature.
• 15:19
  This is the mean payoff or the long run average. So what we do is we take the partial sums of these total weights.
• 15:27
  So we look for all the prefixes, the finite prefixes of a given path, and we take the average for these finite prefixes.
• 15:36
  This is this value here. And then we either take the limits or the limits of.
• 15:44
  For these values Now, given a single pass, then the limit and the limits up, they can be different values.
• 15:51
  However, what is known is that in finite Markov trains that makes no difference whether we deal with the limits or the limit.
• 16:00
  So in expectation, these are the same.
• 16:03
  And this result carries over to two Markov decision processes where the maximum does not change.
• 16:11
  Whether we take the modelling soup and say for the minimum overall calculus.
• 16:16
  Well, and moreover, and I will not zoom into the details,
• 16:21
  there are efficient algorithms to compute a memory less deterministic scheduler where these the max or the minimum achieved,
• 16:31
  and these can be computed using linear programming techniques.
• 16:37
  So now let's go, let's look or let's go more in the direction of the shortest path problem.
• 16:45
  And let's go look first for the discounted case.
• 16:49
  And here the key concept on the so-called bellman equation.
• 16:53
  So this is it was somewhere in the fifties.
• 16:57
  So it's quite a long time ago when he introduced this this bellman equations.
• 17:04
  Okay. So now we are in the disguises. Okay. So the task is to find a schedule that maximises the expected discounted rate.
• 17:13
  And you go, You are the bellman equations. So the idea is to characterise the global maximum by local maxima in every state.
• 17:24
  So. S is a state.
• 17:27
  An X is a variable for the maximal expected discounted rate that can be can achieve from state as so if we treat state as an initial state.
• 17:40
  And then this value x equals the maximum of all the actions that can be taken instead.
• 17:49
  And for each such action, we look for the weight of the state action per alpha, plus the weighted some of these values for the success of.
• 18:03
  And the rates are given by the discount factor gamma multiplied with the transition probability going from s when taking alpha to state t.
• 18:15
  And. This is a recursive equation, so X equals something.
• 18:20
  And T on the right hand side, we have two values for the successors.
• 18:24
  So you can think of it as a function that maps C or vectors this one component for each state to two vectors.
• 18:34
  And what has been shown is that this function, thanks to this discount factor,
• 18:40
  gamma is a contracting map on a banner space, so it has a unique fixed point.
• 18:46
  And this indeed also is the key property to establish algorithms.
• 18:53
  So one of them is derived linear programming techniques.
• 18:58
  Namely, instead of saying X is equals, the maximum, we say x is greater or equal,
• 19:05
  then all these values for each action that can be taken in in status.
• 19:11
  And to ensure that we have access equal to the maximum, we minimise all these values.
• 19:19
  So this is one thing. And the other thing is what can also be derived from this is the value integration.
• 19:27
  So we trust. So this function, if we start with an arbitrary value or zero in every component,
• 19:36
  and then we simply apply successively implied this function F and convergence is guaranteed.
• 19:44
  And that is also a technique I will not speak about, which is called policy iterations of successively improved memory,
• 19:52
  less deterministic scheduler, and eventually destabilises it in an optimal solution.
• 20:01
  So now this was the case, this one here for discounting.
• 20:06
  And remind for totally what I said.
• 20:09
  This is essentially the same, but without this discount factor and indeed the bellman equation itself, they are for this infinite horizon case.
• 20:19
  They still look like this unless it is already one of these distinguished gold states in this case that is simply zero,
• 20:30
  but otherwise did have the same equation. And he was that this contract of gamma, which is one or can be dropped.
• 20:38
  But now things are more difficult. This before I said we have a contracting that.
• 20:45
  But this is not clear here. Not.
• 20:49
  Not in all the cases. We don't have to discount any more.
• 20:53
  So this needs. Additional things to make sure that we have a unique fixed point and so on.
• 21:02
  And all this was. Let's hear we talk about the stochastic sort of path problem.
• 21:09
  And all this research is about these extra things that we need.
• 21:15
  So just I skipped the outline at the beginning,
• 21:18
  but now here comes the what I just did was to give you some basics about the model we talk about and end these important measures,
• 21:27
  and now we talk about the stochastic sort of path problem.
• 21:30
  First the classical one and then later on on on variants.
• 21:36
  So this notion stochastic sort of past problem and the main results, they go back to Betsy and Alex from the year this is very small.
• 21:49
  It is 9 to 1 in a paper published in Mathematics of Operations Research,
• 21:57
  and in this paper they have a very nice section on the related work or summary of
• 22:04
  the work that has been done at this Times was summary of the state of the art.
• 22:10
  So here is this paper from 91 and it goes back to 62.
• 22:15
  This problem has been investigated first,
• 22:19
  and they also nicely describe that even Apollo tries to introduce a new name for this because
• 22:27
  this was used under different names and the three different three other different names before.
• 22:33
  But they also explain that this is in the style of classical short of path problems which are known from graph theory.
• 22:43
  So now. Let's look for this picture here.
• 22:49
  We have a way to find out State Markov decision process.
• 22:53
  And we have a certain gold state, which is the type of state that we want to reach, and we accumulate the rates until we reach this gold state.
• 23:03
  And then we want to reason about the mean or maximal expectation for this random variable.
• 23:10
  Now for the rest of the talk, I will consider the longest pass problem we have here to the maximum.
• 23:17
  The techniques for minimum are completely analogous.
• 23:23
  So the first result, and this goes back to the late sixties was that in the special case where under
• 23:32
  every sketch you scapula or the minimal probability to reach the gold state is one.
• 23:39
  In this case, what have been proven is that the bellman equations, they still work.
• 23:46
  And they get a contracting rep. So who empty piece of this form out called contracting MIPS.
• 23:53
  And these are exactly the you see free notes that do not have any components.
• 24:00
  And it was shown that there is a reduction to the discounted case in this case.
• 24:07
  So all this machinery for discounted rate works also for this case.
• 24:12
  Now the contribution of that take us to thecase was this requiring that under every catalogue we reach gold state.
• 24:21
  It's a very strong requirement. Now let's relax it by considering only those catalogues, what they called the proper catalogues,
• 24:33
  namely those that reach the goal of the probability one.
• 24:36
  But there might be others. So. And.
• 24:41
  They also achieved that under certain conditions.
• 24:45
  We can still rely on these Belmont equations and techniques that have been developed for the discounted case,
• 24:52
  but they needed a second condition here, which is that that the total expected total weight under each improper scheduler.
• 25:03
  So each scheduler that. Does not reach the gold state with probability one.
• 25:11
  Must be minus infinity. And they showed that if these two conditions hold it, then the maximum is indeed finite.
• 25:21
  And all this machinery that has been developed for the discounted case still works.
• 25:27
  So. So now the question is.
• 25:33
  How to track this condition. The second condition, the first one, this is this is simple.
• 25:38
  They agree to do it in polynomial time.
• 25:44
  But how to track this condition? The second one. And the next thing is a.
• 25:50
  So if these two conditions hold, then the maximal expectation is finite.
• 25:55
  But there can be other cases where the maximal expectation is finite.
• 25:59
  So it's not a complete criterion.
• 26:02
  So what to do in this case is wait to find out how to check this and how to compute in these cases an optimal catalogue and the optimal value.
• 26:14
  And the first answer was given to these questions was given by look at Alpha Howell in his Conquer 99 paper,
• 26:21
  where he considered Markov decision processes where the weights have all the same polarity that they are all known positive or they are all negative.
• 26:32
  And what he did was he provided a transformation to the case of peptic ulcer and
• 26:38
  to clear case so that these two conditions hold for a transformed and repeat.
• 26:45
  And the idea here for the case this is now for the case with all weights are non positive, so either negative or zero.
• 26:53
  Then you observe the following whenever you have an end component where every state action pairs meet zero,
• 27:01
  then you can collapse them to a single state. Then it's no longer an end component.
• 27:08
  And. In that way, you can remove all these end components consisting of what I call zero end components.
• 27:17
  And what remains is an MDP, where each end component contains at least one state action pair.
• 27:24
  This negative weight and the other rates are non-negative, non positive anyway, which gives you that expectation.
• 27:31
  The expected value of the total weight is indeed minus infinity for each improper scatterplot.
• 27:39
  And in the case where all the rates are non-negative, then Alpha proved the following.
• 27:47
  This makes the maximal expectation is finite.
• 27:51
  If and only if the weights in all end components are zero.
• 27:56
  So no end component contains the stated comparative positive weight.
• 28:02
  And in that case one can do the same thing. One collapses all the zero and components and the result is an MDP that has no improper scapula at all.
• 28:14
  The all that did the remaining to the end.
• 28:17
  If all these and components enjoy this, then after this collapsing the zero and components, there are no end components anymore.
• 28:26
  And these these concepts can also be generalised for the case of arbitrary interrogates.
• 28:34
  So we can have a mixture between positive and negative rates.
• 28:38
  And let's have quickly a closer look in this criterion pool for finite nodes and and for this transformation.
• 28:52
  There is some cleaning up to make sure that from every stage we can reach the goal with
• 28:57
  state of this with probability one and that none of the states are removed and so on.
• 29:03
  I will skip this. Then, after such a cleaning up, the result or characterisation of the finite notes looks like this.
• 29:12
  The maximal expectation is finite. If and only if the MDP has no great divergent end component and component is said to be very
• 29:23
  divergent if it has a schedule such that for almost all the passes along this catalogue,
• 29:31
  the limbs of these prefixes of the weights.
• 29:36
  Hence to infinity. Now, this observation then yields an algorithm for checking finite nodes.
• 29:44
  Compute the maximal and components. This can be done with an iterative, strongly connected component computation in patriotic time,
• 29:55
  and then one can track this with divergence separately.
• 29:59
  To give you an idea for that, let's have a closer look.
• 30:02
  So. This was again, the definition of great divergent and components.
• 30:09
  They exist as catalogues such that almost surely the same look tends to plus infinity.
• 30:16
  One special case also called Pumping and Components.
• 30:20
  The same thing holds, but now in a stronger form. Namely, even the live in goes to plus infinity.
• 30:27
  This, for instance, applies to the end component, which is your trust mark of train, which is completely uniform.
• 30:35
  So if interest is uniform, probability will stay in that state or go to the other state.
• 30:41
  And one state for one state, we have to wait plus two and four out of one minus one.
• 30:47
  Then if you look for the accumulated weight on most trawler,
• 30:51
  it goes up and up and up and higher and higher and higher such that indeed the limits will be plotted infinity.
• 30:59
  Another extreme situation is what we called what has been called gambling and component.
• 31:06
  The limit goes to minus infinity and super goes to plus infinity.
• 31:12
  So we still have this divergence condition here on the right hand side.
• 31:17
  So this would be the case where this accumulated rate oscillates.
• 31:22
  So it goes down and down. So up and down and up and down and so on.
• 31:30
  So now here comes an algorithm to track rate divergence.
• 31:36
  Assuming that we have a strongly connected Markov decision process and this assumption is justified because, as I said before,
• 31:44
  to take this finite ness of the maximal expectation, it is sufficient to analyse the maximal end components separately.
• 31:52
  So we are in this strongly connected case. So we first compute the maximal mean pair off and a corresponding memory deterministic scheduler.
• 32:06
  If this mean payoff is positive. Then we can safely return.
• 32:11
  Yes, because just remember, the mean payoff was defined as the average of the rates that we collect in the first steps,
• 32:19
  and then the end goes to infinity. So if this is the case, if even this mean payoff is positive, then we are in a pumping case.
• 32:29
  If the mean of of this catalogue or the maximum of is negative, then we can safely return.
• 32:37
  No. This is not the case. It cannot be divergent because the maximal expected mean pair of in all and components must be negative.
• 32:48
  So when we return, when we arrive here, I thought then need a tool, not three of flights.
• 32:55
  So between that expected mean pay of what a maximum of is zero.
• 33:02
  Now this catalogue sequence is a memory list. Deterministic scheduler induces a Markov trade.
• 33:10
  Now this mark of trade, you can consider it as a graph.
• 33:13
  It has certain strongly connected components.
• 33:17
  And now look for those that are at the bottom that cannot be left.
• 33:21
  Pick one of them.
• 33:23
  So if this one is compelling and reminder, this means that the name goes to plus infinity to minus infinity, then we can safely return.
• 33:35
  Yes, because gambling implies rate divergence. The question is how to track this being gambling or not.
• 33:45
  This is an NPR problem in general. But here we are in a similar case.
• 33:50
  We have a Markoff train. So this is indeed a Markoff train.
• 33:55
  And we know that the mean payoff is zero. But then being gambling is equivalent to the existence of cycles where the accumulated weight is positive,
• 34:07
  which again is equivalent to the statement that there are cycles where the accumulated weight is negative.
• 34:14
  So and this is a simple graph condition. So this can be also tracked by graph.
• 34:23
  Now, what remains to consider is the case that this is not complete.
• 34:29
  But then. But then the only thing what can still apply is that all the state action pass in the end component, or at least PSC must have made zero.
• 34:44
  All the cycles must have zero before effort.
• 34:48
  The criterion is to check the existence of positive cycles, which is equivalent to the existence of negative cycles.
• 34:55
  And what if this does not apply? Then this means that the accumulated rate along all the cycles must be zero.
• 35:02
  And in that case. What we can do is we can somehow flatten and such and components.
• 35:11
  Now, in the case of non positive and non-negative weights, I said we simply collapse them to a single state.
• 35:19
  Yet the situation is a bit more complicated.
• 35:23
  But if I look at the time, then I think I will keep this.
• 35:30
  If you like to see it, I'm happy to show it after to talk.
• 35:35
  No. So.
• 35:43
  Well in the end with this technique to remove.
• 35:47
  And components are indeed back to exactly this picture of what I have shown you for the case for Fallujah as I was case.
• 35:56
  Not positive or negative weight.
• 35:58
  There is a transformation which is polynomial time to a new MGP that satisfies the constraints that are considered by Betsy us and
• 36:09
  is such that we can rely on their machinery and rely on all these techniques that have been developed for the discounted case.
• 36:18
  So let's look for variance and let's start.
• 36:27
  Yeah. This. A few questions.
• 36:30
  Why do we consider variants? The first thing is.
• 36:35
  I said to you, we consider the maximum overall the proper schedule of low dose schedules that reach the goal stage with probability one.
• 36:45
  Is it really justified to ignore the improper ones?
• 36:49
  And what is the case if there are no proper schools at all?
• 36:53
  If all this catalogues fail the Golden State with some positive probability.
• 36:59
  And another question.
• 37:02
  Just looking for the expectation, then this might not be the best solution if the maximal optimal schedule is a good expectation.
• 37:13
  Okay. But the variance is very, very high.
• 37:17
  Then there is a very high risk that concrete simple runs have the accumulated weight much less than the expectation.
• 37:28
  So in these cases it might be better to have suboptimal sub maximal expectation but a better, smaller variance.
• 37:38
  Looking for the variance. I find it a bit surprising.
• 37:43
  This is surprisingly difficult. So a natural thing would be to have the lowest threshold values.
• 37:51
  I want to have at least this and that expectation.
• 37:54
  And I have a threshold and an upper bound for the variance.
• 38:00
  No such threshold problems, at least to the best of my knowledge.
• 38:03
  It is not known to be solvable. What is known is to achieve such thresholds or to satisfy such threshold conditions.
• 38:12
  One might need schedules that use both memory and randomisation.
• 38:18
  But I'm not aware that there is any solution that is known.
• 38:24
  There is a partial answer, but for a much simpler setting, namely, if there might be difference catalysts that achieve the maximal value.
• 38:34
  And if you consider only those and you seek for very minimal schedule on the dose that achieve the maximum, then the situation is simpler.
• 38:45
  More or less one can use bellman like equations for the variants.
• 38:51
  And what makes it so simple is. In the in this with this question here, the expectation is fixed.
• 38:58
  It is a fixed value that can be computed before and then it can be treated as a constant in this linear program.
• 39:05
  So all this catalogues under consideration here.
• 39:09
  They have all the same expectation and this makes it simpler.
• 39:13
  This problem. So another thing is to look at what have people done in risk theory.
• 39:20
  So there is a notion called variance penalised expectation.
• 39:26
  So what they do in this context here we still want to have good high expectation is to
• 39:33
  take the supreme of all its catalogues that can be achieved for this goal function.
• 39:39
  Here we take the expectation, the expected accumulated weight minus some factor lumped on some putative value times the variance.
• 39:50
  So there is some incentive not only to maximise the expectation but also to look for a small variance value.
• 40:01
  For solution methods for these. I come to this in a second.
• 40:05
  There is a partial answer. Another measurement also taken from risk theory is the so-called conditional value at risk,
• 40:13
  which has been investigated by Kaczynski and to be a second offer.
• 40:19
  So this value at risk would fix some some probability value or some percentage.
• 40:27
  Pete And you are interested what happens in the worst cases.
• 40:32
  So in the 10% worst case for this, you can define the so-called value of risk here.
• 40:39
  So where it swaps? What are the worst cases?
• 40:43
  Let's let's say it in that way. And then you look here in this conditional case, what is the the the expected, uh, accumulated rate.
• 40:54
  In exactly these cases, these p worst cases.
• 40:59
  But that's what they do. Solution method.
• 41:03
  I will talk in a second. Uh, or so.
• 41:07
  This was already a conditional expectation. But also, you can look for this in a clear form.
• 41:13
  The conditional expected accumulated weight under the assumption that we indeed reach the goal state.
• 41:20
  This makes it possible to relax this assumption that we only look for the schedules that achieve the goal of this probability one.
• 41:28
  Instead, it is sufficient to look for those that reach the goal state at all.
• 41:34
  And another variant of this one, which is conceptually close to this one, is what we what has been called partial expectations.
• 41:45
  So for this random variable, we say take the accumulated weight in case that we did reach the gold state and otherwise zero.
• 41:57
  Now these problems look quite different, but they have some similarities.
• 42:03
  And I will briefly zoom into conditional expected accumulated rewards and then give you an idea of what are the similarities to these other problems.
• 42:18
  So, uh, the first thing, why should we interested in these conditional expectations?
• 42:24
  Well, it's a natural measure. For instance, if you have probabilistic non deterministic programs,
• 42:31
  then you might be interested in the conditional expectation time under the assumption that the program indeed terminates.
• 42:39
  Or you might look for certain failure scenarios.
• 42:44
  And then what are the expected costs of repair protocols in these particular failure scenarios which can suit your condition?
• 42:53
  And it has also been used for some kind of multi objective reasonings with cost utility to analyse the cost utility trade of its captive.
• 43:05
  It is more difficult than the standard, uh, stochastic sort of past problem because as you will see in a second,
• 43:13
  optimal memory, less credulous might not exist anymore.
• 43:17
  We might need history. And also this using linear programming techniques in this naive form, this one variable state won't work anymore.
• 43:30
  So let's look at an example, namely this one here.
• 43:35
  So this is an empty pig where it is just a single state where we have a non
• 43:40
  deterministic choice as to where we can go with an alpha directly to the gold state.
• 43:46
  It's probability one. Or we can take action beta with the self loop here or going to a failed state.
• 43:55
  So let's look first for the two deterministic schedulers memory less deterministic schedules that always do the same thing when they are in state.
• 44:06
  So the first option is always take action undefined state as to then.
• 44:12
  We have to be have trust. A single pass going to to pass is going to go with oneness from aethereal via one to goal.
• 44:22
  Then we collect the reward for this action, which is all.
• 44:27
  And the other one goes from zero to S2 and then to gold and into the reward zero.
• 44:32
  So the result is a half. But this catalogue, the minimalist,
• 44:40
  deterministic catalogue which always chooses beta in state as to then achieve a better conditional expectation namely are.
• 44:50
  And this is because they stressed a single pass going to goal.
• 44:54
  While as one we achieve the value, the reward order to the weight are for gamma and the other possibility for this conditional expectation.
• 45:07
  We never reach goals. We simply cannot. So it was a beta is better than alpha.
• 45:17
  But we can do better. Let's look for the following schedule in state as to for the first and visits we take beta and for the end plus first visit.
• 45:29
  If we have taken the self loop. If it happens that we have taken the self loop and times.
• 45:35
  Then we take action. So there is still this possibility.
• 45:42
  Going directly from zero to S1 to goal.
• 45:46
  This stands for this one half times are. Plus now one half times the probability to take this self loop and times.
• 45:57
  This is this value. And whenever we take beta, we own this great one.
• 46:03
  So all together we get to the factory in. Now you can calculate.
• 46:08
  Then the result would be this. And this is better than or remind.
• 46:14
  This was the conditional expectation that we achieve with this memory less deterministic scheduler which always chooses beta.
• 46:21
  So this value is larger than our if and only if this number n is larger than R, and one can compute that the maximum is achieved when equals plus two.
• 46:33
  Now, what this example shows is. We can eat memory.
• 46:39
  So in this case, we need a counter for the number of we have taken this self loop.
• 46:48
  And what is meant by your biting local reasoning is not sufficient.
• 46:54
  I trust that the optimal value is achieved for this cat.
• 46:59
  After our plus two visits, as to we take extra alpha.
• 47:04
  Now, this depends on all which is the rate of this action gamma, which is sitting here.
• 47:10
  So this condition is even not reachable from S2.
• 47:14
  Just looking for the MDP that is reachable from is too.
• 47:19
  We cannot see anything about the optimal behaviour in state as to.
• 47:23
  This is what I mean here is with local reasoning is not sufficient.
• 47:29
  And there is also another phenomenon which does not occur in the in the unconditional case.
• 47:36
  For the initial state. The maximal expectation is finite.
• 47:42
  But. Oops. Prostate is too.
• 47:47
  If I consider this as the initial state,
• 47:50
  then indeed this maximal conditional expectation is infinite because I have the possibility to pump at infinity.
• 47:59
  And go then to two to the gold state.
• 48:04
  So, uh, now, although in the interest of time, I will just mention the results and skip these, these details here.
• 48:14
  Uh, if there is a method, though, this was on the previous slide, there is.
• 48:20
  There are graph techniques to check finite.
• 48:24
  So assuming that we have tracked this and made sure that the conditional expectation is finite and assume that all rates are non-negative,
• 48:35
  either positive or zero, but no negative values.
• 48:40
  Then what can be shown is that the threshold problem.
• 48:43
  So to check whether this maximum conditional expectation is beyond a certain threshold.
• 48:49
  This is a piece based hard problem and piece based complete in ethically case.
• 48:56
  Now for algorithms in the in the non to click case the way we have cycles.
• 49:02
  The key observation is there is what we called a saturation point.
• 49:07
  So if there is some natural number such that whenever we reached a configuration
• 49:16
  state and look for the accumulated weight that has been accumulated so far,
• 49:21
  if this one is larger than this operation point, then from then on the best what can do is to maximise the probability of reaching a gold state.
• 49:31
  And the intuition is. The accumulated weight is already so high that that we want to save.
• 49:39
  We do not want to go. The risk that that we fail to visit the ghost state, in which case we lose everything.
• 49:45
  That's that's the intuition behind this.
• 49:49
  Well, from this one, one can derive an exponential time threshold algorithm and an exponential time algorithm to compute this optimal value.
• 50:01
  Now, this was this was saturation point algorithm for the case of conditional expectation.
• 50:08
  And now remember that I mentioned before other variants, the same observation with these separation points have been made for partial expectation.
• 50:21
  This is the result by my test group.
• 50:25
  The antidote has also been made for conditional values for risk.
• 50:29
  This is the result by gift making of them. And.
• 50:35
  It also applies to the setting of variance penalised expectations reminder that the goal was to
• 50:42
  maximise the objective expectation minus lumped times variants slumped up being from positive constant.
• 50:52
  And he is also said to raise a point, but here comes some strange phenomenon behind that.
• 51:02
  Saturation point. The best thing one can do is to minimise the probability to reach the gold state.
• 51:09
  And the reason it's more or less intuitively, this variance is a quadratic function.
• 51:19
  And from some point on in this objective, the variance becomes the dominant thing.
• 51:25
  And so what one wants to do is to to minimise that from some point on.
• 51:32
  One wants to avoid that the value gets too high. That's, that's the intuition behind that.
• 51:39
  Which at the same time makes this very polite expectation in this context a bit questionable.
• 51:47
  Earth and other taking other things flipped on the owner of a click empty piece with interest rates.
• 51:54
  Then it's not a problem because in the case we only have finite many pasts.
• 52:01
  They can be explored using purely space algorithms.
• 52:05
  And for many of these problems, I think even for all AP space, lower bound have been established for this case.
• 52:17
  So now so this word restrictions, non-negative weights or etc.
• 52:24
  Now what is in the training case? And one indication that this is more difficult is that these values,
• 52:32
  the maximal expectation defined in one of these variants can be an irrational value.
• 52:38
  So one should not expect linear programming techniques as they are known for the unconditional case.
• 52:44
  And indeed, what the result of Jakob Bauer in his Ph.D. thesis.
• 52:51
  What he has shown is that quite a lot of these problems are Coulomb or even positivity of heart.
• 53:00
  Now, this column problem is a very prominent and very old problem in mathematics to decide whether a recurrent sequence eventually
• 53:10
  hits zero or whether all these values are positive and the desired ability status is unknown for quite a long time.
• 53:21
  Ben, Do you know I forgot when this column problem of positivity has been considered first?
• 53:29
  Or anyone. In the.
• 53:37
  That okay. In the 17th. So quite old problem.
• 53:43
  Um. So trust the site remark.
• 53:47
  Uh, well, I say I was surprised to see these results, that these problems are so hot.
• 53:54
  And Jaco introduced to my opinion, a very elegant proof technique.
• 54:00
  So he used. The same MVP get hit for for encoding linear recurrent sequences to prove school m or positivity hardness for a wide range of problems.
• 54:15
  Although for other problems which have nothing to do with weights like the model tracking problem for frequency
• 54:22
  l t l in Markov decision processes or threshold conditions for termination probabilities in one counter MVP.
• 54:32
  And these reductions, they only differ in the truth of the in the choice of the initial condition.
• 54:40
  So let's come to the conclusions. So for the classical stochastic sort of past problem, the key development equations from which we have to.
• 54:52
  This full machinery tool that can be exploited algorithmically.
• 54:56
  So linear programming techniques, value optimisation, policy, iteration, and let's say.
• 55:04
  To get there were first. These are kind of semantic site conditions that take us a tricky approach.
• 55:12
  But after some graph transformations, polynomial time transformations, one can reduce to this case.
• 55:22
  Now for these variants that that I proposed here or that have been considered in the literature,
• 55:29
  I found it surprising that they are so difficult in the case of introverts, this positivity,
• 55:36
  hardness and quite a few of them enjoy this property that if all debates are non-negative,
• 55:42
  then one can exploit the non-monetary necessity of the accumulated weights along the prefixes,
• 55:50
  which gives you a saturation point characterisation and then X time or X based algorithm.
• 55:59
  And one. Oops. One other remark. So this was for Markov decision process, which are also considered as one player stochastic games.
• 56:10
  Now in the case where you have to play us. Then let's say the objective of one player is to maximise this expectation and for the
• 56:22
  other player to minimise the awesome results by putting in better outcomes from 99.
• 56:30
  But at least to the best of my knowledge, this problem has not been completely solved.
• 56:37
  And there is also this. This I mentioned this, this partial of expectations.
• 56:44
  This also amount of paper has been considered also in the case of of the game setting.
• 56:52
  But I'm not real for algorithms, for the conditional expectation or the other variance of the to have the shortest pass problem.
• 57:01
  Now, I almost made it in time. Thank you very much.