1 of 60

2 of 60

Lecture 10: Policy Classes + Robust Optimization

2

No online Quizz today, just open-end questions

The Lecture will be recorded

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

3 of 60

Course Plan

3

DTU Compute

24 May 2023

4 of 60

Agenda for today

4

  1. Consolidate what we have learned
  2. Reflect on limitations / considerations
  3. Sneak-peak into some additional concepts / aspects

DTU Compute

24 May 2023

5 of 60

Back to the Big Picture

5

Define

Design

Evaluate

 

 

MDP

Agent

Environment

Optimizing�Decisions

Designing Policies

DTU Compute

24 May 2023

6 of 60

Back to the Big Picture

6

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

Optimizing�Decisions

Designing Policies

DTU Compute

24 May 2023

7 of 60

Back to the Big Picture

7

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

*In this course, to avoid dealing with the modeling part, we have assumed that the real system and the model you have are the same thing. They are not. So, an optimal decision for the model, does not necessarily mean an optimal (or even good) decision for the real system.

DTU Compute

24 May 2023

8 of 60

Back to the Big Picture

8

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

Actually, we can often choose the time granularity, or even construct a hierarchical combination of policies.

DTU Compute

24 May 2023

9 of 60

Back to the Big Picture

9

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

We have been assuming that states are given and observable. Actually, you can choose what you model as state variables, including hidden state variables.

DTU Compute

24 May 2023

10 of 60

Back to the Big Picture

10

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

We have been assuming that decisions are given. Actually, sometimes you can choose what levers you pull.

DTU Compute

24 May 2023

11 of 60

Back to the Big Picture

11

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

We have been assuming that the dynamics are given. Actually, you need to model them and the choice of model is a strategic one: it should be co-designed with the policy.

DTU Compute

24 May 2023

12 of 60

Back to the Big Picture

12

Define

Design

Evaluate

 

 

 

MDP

Agent

Environment

We have been assuming that the cost function is given and conducive (e.g. linear). Actually, we are often given problems that are not rigorously defined, have complex metrics (think e.g. risk), or they even feature qualitative and/or multiple objectives.

DTU Compute

24 May 2023

13 of 60

Agent vs Environment

13

 

The environment is a simulator of the real system�i.e. the agent’s action is applied to it (input) and it returns the next state and the reward (output).

The agent may internally model the environment (namely, the state dynamics) to account for the future. But it does not have perfect foresight over the future nor does it have an accurate model necessarily.

DTU Compute

24 May 2023

14 of 60

Agent vs Environment

14

 

The environment is a simulator of the real system�i.e. the agent’s action is applied to it (input) and it returns the next state and the reward (output).

The agent may internally model the environment (namely, the state dynamics) to account for the future. But it does not have perfect foresight over the future nor does it have an accurate model necessarily.

Policies should be compared under the same experiments

DTU Compute

24 May 2023

15 of 60

Policy Classes

15

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

16 of 60

Policy Classes

16

Policy Class

Description

Formulation

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

17 of 60

Policy Classes

17

Policy Class

Description

Formulation

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

18 of 60

Policy Classes

18

Policy Class

Description

Formulation

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

Policy Function Approximation

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

19 of 60

Policy Classes

19

Policy Class

Description

Formulation

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

Policy Function Approximation

​

​

Cost Function Approximation

​

​

Greedy Deterministic Optimization but imposing a heuristic Slack, or a Penalty for aggressive actions

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

20 of 60

Policy Classes

20

Policy Class

Description

Formulation

Strengths

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

​

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

​

Policy Function Approximation

​

​

​

Cost Function Approximation

​

​

Greedy Deterministic Optimization but imposing a heuristic Slack, or a Penalty for aggressive actions

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

21 of 60

Policy Classes

21

Policy Class

Description

Formulation

Strengths

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Directly simulates the future, handles constraints, conceptually simple / intuitive

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

​

Policy Function Approximation

​

​

​

Cost Function Approximation

​

​

Greedy Deterministic Optimization but imposing a heuristic Slack, or a Penalty for aggressive actions

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

22 of 60

Policy Classes

22

Policy Class

Description

Formulation

Strengths

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Directly simulates the future, handles constraints, conceptually simple / intuitive

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

Fast, captures long-term effects / delayed rewards, can be trained arbitrarily well (offline)

Policy Function Approximation

​

​

​

Cost Function Approximation

​

​

Greedy Deterministic Optimization but imposing a heuristic Slack, or a Penalty for aggressive actions

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

23 of 60

Policy Classes

23

Policy Class

Description

Formulation

Strengths

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Directly simulates the future, handles constraints, conceptually simple / intuitive

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

Fast, captures long-term effects / delayed rewards, can be trained arbitrarily well (offline)

Policy Function Approximation

​

​

Very fast, parametric policy form, capitalizes on expert knowledge, relatively easy to implement/maintain.

Cost Function Approximation

​

​

Greedy Deterministic Optimization but imposing a heuristic Slack, or a Penalty for aggressive actions

​

​

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

24 of 60

Policy Classes

24

Policy Class

Description

Formulation

Strengths

Direct Lookahead

Optimize Decisions over a Lookahead horizon

​

​

Directly simulates the future, handles constraints, conceptually simple / intuitive

Value Function Approximation

​

Optimize the current reward + the Value of the next state

​

​

Fast, captures long-term effects / delayed rewards, can be trained arbitrarily well (offline)

Policy Function Approximation

​

​

Very fast, parametric policy form, capitalizes on expert knowledge, relatively easy to implement/maintain.

Cost Function Approximation

​

​

Greedy Deterministic Optimization but imposing a heuristic Slack, or a Penalty for aggressive actions

​

Fast, very intuitive, capitalizes on domain experience, interpretable, easy to implement/ maintain, skips modelling

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

25 of 60

Considerations for designing a policy

25

First of all, remember to start simple and only introduce complexity gradually as needed.

  • How accurately can the transition dynamics be modeled?
  • Are the states exogenous or endogenous?
  • Do they evolve stochastically or deterministically?
  • Are the state and action spaces low or high dimensional?
  • How much time is there to make a decision (online)?
  • Does the MDP have delayed rewards or temporally-coupled (critical) constraints?
  • Is there access to expert knowledge?
  • How important is policy interpretability?

The ultimate test is evaluating and comparing policies in a good simulation environment.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

26 of 60

Evaluating a policy

26

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

27 of 60

Evaluating a policy

27

  • Mean
  • Variance
  • Confidence (e.g. 95th percentile)
  • Worst-case
  • Performance under stress

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

28 of 60

Evaluating a policy

28

  • Mean
  • Variance
  • Confidence (e.g. 95th percentile)
  • Worst-case
  • Performance under stress

Value of perfect information

Value of stochastic solution

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

29 of 60

Evaluating a policy

29

  • Mean
  • Variance
  • Confidence (e.g. 95th percentile)
  • Worst-case
  • Performance under stress

Value of perfect information

Value of stochastic solution

+ considerations about:

modularity, maintenance/adaptability, interpretability, resilience (e.g. under failed components), and more.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

30 of 60

Evaluating a policy

30

How many experiments are enough?

  • Mean
  • Variance
  • Confidence (e.g. 95th percentile)
  • Worst-case
  • Performance under stress

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

31 of 60

Evaluating a policy

31

  • Mean
  • Variance
  • Confidence (e.g. 95th percentile)
  • Worst-case
  • Performance under stress

How many experiments are enough?

Up until the distributional properties of this empirical distribution stabilize between experiments

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

32 of 60

Evaluating a policy

32

Should we also evaluate how often the policy violates the constraints?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

33 of 60

Evaluating a policy

33

Generally, critical systems have backup safety protocols. So, infeasible decisions are mapped back to the feasible set through some overrule.

Should we also evaluate how often the policy violates the constraints?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

34 of 60

Evaluating a policy

34

Generally, critical systems have backup safety protocols. So, infeasible decisions are mapped back to the feasible set through some overrule.

However, this is tricky for intertemporal constraints, which could call for an ex-post evaluation.

Should we also evaluate how often the policy violates the constraints?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

35 of 60

Evaluating a policy

35

What if the environment model is wrong?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

36 of 60

Robust Optimization

36

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

37 of 60

MPC

37

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

38 of 60

MPC

38

L

1 2 ... 22 23 24

 

 

 

 

 

Forecast

Realization

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

39 of 60

The student’s problem revisited

39

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

40 of 60

The student’s problem revisited

40

 

 

 

 

 

Under this policy, am I guaranteed to pass the course?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

41 of 60

The student’s problem revisited

41

 

 

Under this stochastic policy, am I guaranteed to pass the course now?

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

42 of 60

The student’s Robust Optimization problem

42

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

43 of 60

Robust Optimization: Box Uncertainty Sets

43

 

 

 

 

 

Can we solve this problem?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

44 of 60

Robust Optimization: Box Uncertainty Sets

44

 

 

 

 

 

Can we solve this problem?

We have infinitely many constraints.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

45 of 60

Robust Optimization: Box Uncertainty Sets

45

 

 

 

 

 

Can we solve this problem?

We have infinitely many constraints.

But, we know what the worst-case is…

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

46 of 60

Robust Optimization: Box Uncertainty Sets

46

 

 

 

 

 

Can we solve this problem?

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

47 of 60

Robust Optimization: Box Uncertainty Sets

47

 

 

 

 

 

Can we solve this problem?

 

This is way too conservative…

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

48 of 60

Robust Optimization: Polyhedral Uncertainty Sets

48

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

49 of 60

Robust Optimization: Polyhedral Uncertainty Sets

49

 

 

 

 

 

Again, we have infinitely many constraints.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

50 of 60

Robust Optimization: Polyhedral Uncertainty Sets

50

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

51 of 60

Robust Optimization: Polyhedral Uncertainty Sets

51

 

 

 

 

 

Again, we have infinitely many constraints.

But now, the worst-case uncertainty realization is itself an optimization problem.

So, we can get rid of the infinitely many constraints, at the expense of having an inner optimization problem.

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

52 of 60

Robust Optimization: Polyhedral Uncertainty Sets

52

 

 

 

 

 

Again, we have infinitely many constraints.

But now, the worst-case uncertainty realization is itself an optimization problem.

So, we can get rid of the infinitely many constraints, at the expense of having an inner optimization problem.

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

53 of 60

Robust Optimization: Polyhedral Uncertainty Sets

53

 

 

 

 

 

Again, we have infinitely many constraints.

But now, the worst-case uncertainty realization is itself an optimization problem.

So, we can get rid of the infinitely many constraints, at the expense of having an inner optimization problem.

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

54 of 60

Robust Optimization: Polyhedral Uncertainty Sets

54

 

 

 

 

 

Again, we have infinitely many constraints.

But now, the worst-case uncertainty realization is itself an optimization problem.

So, we can get rid of the infinitely many constraints, at the expense of having an inner optimization optimization problem.

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

55 of 60

Robust Optimization: Polyhedral Uncertainty Sets

55

 

 

 

 

 

Again, we have infinitely many constraints.

But now, the worst-case uncertainty realization is itself an optimization problem.

So, we can get rid of the infinitely many constraints, at the expense of having an inner optimization optimization problem.

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

56 of 60

Robust Optimization: Polyhedral Uncertainty Sets

56

 

 

 

 

 

Again, we have infinitely many constraints.

But now, the worst-case uncertainty realization is itself an optimization problem.

So, we can get rid of the infinitely many constraints, at the expense of having an inner optimization optimization problem.

 

 

Thus, we can drop the optimization operator and we have a standard MILP

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

57 of 60

Examples of Robust Optimization with Polyhedral Uncertainty Sets

57

Power system operation

Wind generation is geographically correlated

​

Weather-driven applications (e.g. farming, water dam management)

Rain is uncertain, but “budgeted” throughout a year.

​

Logistics (incl. airlines, tracks, inventories)

Delay events are unpredictable but “rare”.

​

Group for course project

People can free-ride but (hopefully) not all group members.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

58 of 60

Next Week: Multiple decision-makers

58

DTU Compute

24 May 2023

59 of 60

Questions and Survey

59

DTU Compute

24 May 2023

60 of 60

Game Quiz

60

DTU Compute

24 May 2023