Cadenas de Markov controladas: Robustez distribucional y

Cadenas de Markov controladas:Robustez distribucional y aplicacionesal control de posicion de un drone de

4 helices

Cristhian Camilo Sanchez fino

Universidad de los Andes

Facultad de Ciencias, Departamento de Matematicas

Bogota, Colombia

2019

Cadenas de Markov controladas:Robustez distribucional y aplicacionesal control de posicion de un drone de

4 helices

Cristhian Camilo Sanchez Fino

Trabajo de grado presentado como requisito para optar al tıtulo de:

Matematico

Director(a):

Mauricio Jose Junca Ph.D. Industrial engineering and operations research

Universidad de los Andes

Facultad de Ciencias, Departamento de Matematicas

Bogota, Colombia

2019

A mi familia

Agradecimientos

Agradezco profundamente al profesor Mauricio Junca, profesor asociado del departamento

de Matematicas de la Universidad de los Andes por su paciencia y apoyo en la comprension

de la teorıa involucrada y en la elaboracion de este proyecto. Tambien agradezco al profesor

Luis Felipe Giraldo, profesor asistente del departamento de Ingenierıa Electrica y Electroni-

ca, por su asesoramiento en la implementacion de este proyecto en un entorno de control.

v

Resumen

En el presente documento, se estudia el concepto de procesos de decision de Markov dentro de

un contexto de optimizacion y de control. Por un lado, se estudian problemas de optimizacion

estocastica. En particular, se estudian problemas de optimizacion robusta distribucional, en

los cuales se asume que la verdadera distribucion de la variable aleatoria involucrada subyace

en un conjunto conocido, denominado conjunto de ambiguedad. En este trabajo, se consi-

dera la estructura del conjunto de ambiguedad a partir de la metrica de Wasserstein en el

espacio de medidas de probabilidad. A partir de resultados de la optimizacion convexa, se

estudia el problema de optimizacion en concreto y su formulacion dual a partir del principio

de dualidad de Kantorovich. Ası, a partir de un enfoque centrado en los datos de muestreo,

se logra obtener un problema tratable que se puede resolver numericamente. Paralelamente,

se estudia la implementacion de la estructura de los procesos de decision de Markov de ho-

rizonte finito enmarcados en el contexto de control del vuelo de un drone de 4 helices.

Palabras clave: Optimizacion, probabilidad, distribuciones de probabilidad, procesos

de decision de Markov, Wasserstein.

Abstract

In this work, the Markov Decision Processes are studied from two different perspectives.

On one side, Stocastic Optimization problems are studied. Particularly, Distributionally ro-

bust optimization problems are studied, in which the real probability distribution of the

random variable is assumed to be part of a known set, which is called the ambiguity set. In

this work, the ambiguity set is defined by the Wasserstein metric on the probability measures

space. Based on the some results of convex optimization, the concrete optimization problem

is studied and its’ dual formulation based on the Kantorovich duality principle. Therefore,

from a data driven approach, a tractable version of the problem is achieved. Paralelly,the

finite horizon Markov Decision processes’ implementation is studied in the context of flight

control of a quadrotor drone.

Keywords: Optimization, probability, probability distributions, Markov decision pro-

cesses , Wasserstein.

Contenido

Agradecimientos IV

Resumen V

1 Introduccion 22 Preliminares 4

2.1 Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.1 Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Resultados relevantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Procesos de decision de Markov(MDP) 9

3.1 Epocas de decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Conjunto de estados y acciones . . . . . . . . . . . . . . . . . . . . . . . . . 93.3 Recompensas y probabilidades de transicion . . . . . . . . . . . . . . . . . . 103.4 MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.5 Reglas de decision markovianas . . . . . . . . . . . . . . . . . . . . . . . . . 103.6 Polıticas markovianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.7 Procesos estocasticos inducidos . . . . . . . . . . . . . . . . . . . . . . . . . 113.8 MDPs de horizonte finito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.8.1 Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.8.2 Criterio de recompensa total esperada . . . . . . . . . . . . . . . . . 133.8.3 Ecuaciones de optimalidad . . . . . . . . . . . . . . . . . . . . . . . . 133.8.4 Optimalidad de polıticas markovianas determinısticas . . . . . . . . . 163.8.5 Algoritmo de induccion hacia atras . . . . . . . . . . . . . . . . . . . 18

4 Optimizacion convexa aplicada a MDPs distribucionalmente robustos usando

la metrica de Wasserstein 194.1 Robustez distribucional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.1.1 Notacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.1.2 Proceso de decision de Markov distribucionalmente robustos . . . . . 194.1.3 Conjuntos ambiguos con metrica de Wasserstein . . . . . . . . . . . . 20

4.2 Optimalidad de polıticas Markovianas . . . . . . . . . . . . . . . . . . . . . . 214.3 Formulacion convexa usando dualidad de Kantorovich . . . . . . . . . . . . . 234.4 Distribucion nominal con soporte finito . . . . . . . . . . . . . . . . . . . . . 264.5 Construccion descentralizada de distribucion en el peor caso . . . . . . . . . 29

5 Aplicacion de MDPs al control de posicion de un drone de 4 helices 315.1 Modelo del drone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.1.1 Arquitectura del modelo . . . . . . . . . . . . . . . . . . . . . . . . . 315.1.2 Parametros de simulacion . . . . . . . . . . . . . . . . . . . . . . . . 33

5.2 Modelo del controlador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.2.1 Definicion de estados y acciones . . . . . . . . . . . . . . . . . . . . . 345.2.2 Definicion de matriz de probabilidad de transicion . . . . . . . . . . . 365.2.3 Definicion de funciones de recompensa . . . . . . . . . . . . . . . . . 365.2.4 Definicion de polıtica de control . . . . . . . . . . . . . . . . . . . . . 36

5.3 Caso de estudio: Seguimiento de trayectoria con MDP de horizonte finito . . 365.3.1 Descripcion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.3.2 Funciones de recompensa . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.4 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.4.1 Analisis de sensibilidad ante la matriz de perturbaciones . . . . . . . 385.4.2 Analisis de sensibilidad ante el tipo de perturbacion . . . . . . . . . . 40

6 Conclusiones y trabajo futuro 416.1 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Contenido 1

6.2 Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41A Optimizacion estocastica distribucionalmente robusta usando la metrica de

Wasserstein 43Bibliografıa 45

1. Introduccion

El presente documento busca comprender los procesos de decision de Markov en distintos

contextos. Los procesos de decision de Markov (MDPs) son una herramienta util para el

modelamiento de toma de decisiones secuenciales, en donde se consideran problemas del

estilo

supπ∈D

Eπ[Ψ(x, ζ)]

en donde la funcion Ψ(x, ζ) corresponde a una funcion que puede representar costos, utili-

dades o recompensas en las que incurre el agente que toma decisiones a lo largo del tiempo,

x las realizaciones de estados y acciones del sistema, ζ es un vector que contiene la infor-

macion de las probabilidades de transicion del sistema y π corresponde a una polıtica que

determina la manera en la que se toman decisiones y cuya estructura esta determinada por

el conjunto D. La principal motivacion para el estudio de los procesos de decision de Markov

es determinar la estructura de las polıticas optimas. Sin embargo, dada la estructura de los

MDPs, la resolucion de este tipo de problemas esta sujeta a la estructura de las probabilida-

des de transicion entre estados, y de las recompensas, que rigen la evolucion del sistema y las

acciones tomadas a lo largo del tiempo. En la gran mayorıa de aplicaciones, no se tiene una

informacion concreta de las probabilidades y las recompensas que rigen el sistema, por esto,

considere a ζ como un vector aleatorio en Rn para algun n adecuado, en el que sus entradas

corresponden a las probabilidades de transicion y las recompensas que rigen el sistema y

considere µ la distribucion de probabilidad de ζ. Entonces, se consideran problemas de la

forma

supπ∈Π

ınfµ∈D

Eπµ[Ψ(x, ζ)]

que se relaciona con los problemas robustos de optimizacion estocastica. En este caso, se

asume que la probabilidad conjunta de las funciones de probabilidad y de recompensas se

encuentran en un conjunto conocido Dde distribuciones de probabilidad. Segun la estructura

del conjunto D el problema adquiere ciertas propiedades que facilitan o dificultan su reso-

lucion. En este caso, varios metodos de rectangularidad han sido propuestos en [5], [4], [8]

para dar una estructura al conjunto D. Para el desarrollo de este trabajo, se quiere estudiar

cuando el conjunto D tiene una estructura derivada de la metrica de Wasserstein.

Finalmente, para comprender la utilidad de los MDPs, se quiere estudiar su aplicacion en el

contexto del vuelo de un drone de 4 helices a manera de motivacion para ilustrar la necesidad

3

de la implementacion de los metodos robustos.

El documento sigue la siguiente estructura: el capıtulo 2 introduce algunos conceptos y

resultados basicos de la teorıa de la optimizacion convexa que seran utilizados a lo largo

del documento. El capıtulo 3 introduce los principales conceptos y resultados de los MDPs

de horizonte finito. El capıtulo 4 introduce los resultados principales en cuanto al enfoque

de optimizacion convexa a los MDPs distribucionalmente robustos a partir de la metrica de

Wasserstein. Finalmente, el capıtulo 5 ilustra la aplicacion de conceptos y resultados de los

MDPs de horizonte finito al contexto de control de vuelo de un drone de 4 helices.

2. Preliminares

La presente seccion busca introducir algunos conceptos basicos de la optimizacion convexa

y alguna resultados relevantes para el desarrollo del proyecto de grado.

2.1. Definiciones

En esta seccion de introduciran definiciones relevantes para el desarrollo del proyecto.

2.1.1. Definiciones

Sea X ⊆ Rm para m ∈ N+. Sea f : X → R, donde R = R ∪ ∞,−∞

Definicion 2.1. f es una funcion cerrada si el conjunto

epi(f) := (x, y)|x ∈ X, y ∈ R, f(x) ≤ y

es cerrado en Rm+1.

Definicion 2.2. f es una funcion propia si f(x) <∞ para al menos un x ∈ X y ∀xf(x) >

−∞.

Definicion 2.3. f es una funcion convexa si para x1, x2 ∈ X, t ∈ [0, 1] se cumple que

f(tx1 + (1− t)x2) ≤ tf(x1) + (1− t)f(x2).

Definicion 2.4. f es una funcion concava si −f es una funcion convexa.

Definicion 2.5. f es una funcion inferiormente semicontinua en x si para toda su-

cesion xk ⊂ X y xk → x se cumple que

f(x) ≤ lım infk→∞

f(xk).

Se dice que f es inferiormente semicontinua en X si es inferiormente semicontinua para

todo x ∈ X.

Definicion 2.6. f es una funcion superiormente semicontinua si −f es inferiormente

semicontinua.

2.2 Resultados relevantes 5

Observacion 2.1. Note que, por la definicion de funciones inferiormente y superiormen-

te semicontinua, se sigue que f es una funcion continua, sı y solo sı f es inferiormente

semicontinua y superiormente semicontinua.

Definicion 2.7. f es una funcion coerciva si para cada secuencia xk tal que ||xk|| → ∞entonces lım

k→∞f(xk) =∞

2.2. Resultados relevantes

Esta seccion introduce resultados relevantes para el desarrollo del presente documento.

Proposicion 2.1. Sea A un conjunto finito. Se define el conjunto

∆(A) :=

x ∈ R|A||xi ∈ [0, 1],

|A|∑i=1

xi = 1

.

Entonces ∆(A)1 es un conjunto cerrado, convexo y acotado.

Demostracion. Cerrado:

Sea f : R|A| → R tal que f(x) =|A|∑i=1

xi. Entonces ∆(A) = f−1(1). El conjunto 1 es

cerrado en R. Luego, basta mostrar que f es una funcion continua, pues ası ∆(A) serıa

cerrado al ser preimagen de un conjunto cerrado. Para esto, note que para ε > 0 se tiene

que para x, y ∈ R|A|

||x− y||2 < δ ⇒|A|∑i=1

(xi − yi)2 < δ2 ⇒ ∀i ∈ 1, 2, . . . , |A| |xi − yi| < δ.

Luego,

|f(x)− f(y)| =

∣∣∣∣∣∣|A|∑i=1

xi −|A|∑i=1

yi

∣∣∣∣∣∣ =

∣∣∣∣∣∣|A|∑i=1

(xi − yi)

∣∣∣∣∣∣ ≤|A|∑i=1

|xi − yi| ≤ |A|δ2.

Entonces, tomando δ =√

ε|A| se obtiene que f es continua.

Convexo:

Sean x, y ∈ ∆(A), t ∈ [0, 1]. Luego,

|A|∑i=1

txi + (1− t)yi = t

|A|∑i=1

xi + (1− t)|A|∑i=1

yi = t · 1 + (1− t) · 1 = 1.

1El conjunto ∆(A) corresponde al simplex de probabilidad sobre el conjunto A

6 2 Preliminares

Entonces, tx+ (1− t)y ∈ ∆(A). Es decir, ∆(A) es un conjunto convexo.

Acotado:

Note que ∀x ∈ ∆(A) se tiene que ∀i = 1, . . . , |A| xi ≤ 1. Entonces,

|A|∑i=1

x2i ≤

|A|∑i=1

1 = |A| < |A|+ 1.

Luego x ∈ B√|A|+1(0), donde B√|A|+1

(0) es la bola abierta de radio√|A|+ 1 centrada en 0.

Es decir, ∆(A) es un conjunto acotado.

A manera de referencia, se enuncian los siguientes resultados del analisis real.

Proposicion 2.2. Sean f, g : X → R funciones con valores reales. Entonces

ınfx∈X

f(x) + ınfx∈X

g(x) ≤ ınfx∈X

f(x) + g(x).

Proposicion 2.3. Sea f : X → R una funcion y sean A ⊂ B ⊆ X. Entonces,

ınfx∈A

f(x) ≥ ınfx∈B

f(x).

Proposicion 2.4 (Proposicion 1.1.2 en [1]). Sea f : Rn → R una funcion propia. Entonces

los siguientes son equivalentes:

(i) El conjunto de nivel Vγ := x|f(x) ≤ γ es cerrado.

(ii) f es inferiormente semicontinua.

(iii) f es cerrada.

Proposicion 2.5 (Teorema de Weierstrass). [Proposicion 3.2.1 en [1]] Sea f : Rn ⊃ D → R,

donde D es el dominio de f y asuma que alguna de las siguientes condiciones se cumple:

1. El dominio de f es acotado

2. Existe un escalar γ tal que el conjunto de nivel

x|f(x) ≤ γ

es un acotado y no vacıo

3. f es una funcion coerciva

2.2 Resultados relevantes 7

Entonces el conjunto de mınimos de f sobre D es compacto y no vacıo.

En particular para X ⊂ Rn acotado y la funcion f definida por

f(x) =

f(x) si x ∈ X ∩D,∞ en caso contrario.

Entonces, El conjunto de mınimos de f sobre X ∩ D es no vacıo y compacto si X es un

conjunto cerrado y f una funcion inferiormente semicontinua en X.

Observacion 2.2. Note que en la proposicion anterior, al tomarse

f(x) =

f(x) si x ∈ X,−∞ en caso contrario,

si la funcion f es superiormente semicontinua y el conjunto X es cerrado, entonces el con-

junto maximos de f sobre X es no vacıo y compacto.

Proposicion 2.6. Sea I un conjunto de ındices y fii∈I , fi : X → R una familia de

funciones inferiormente semicontinuas. Entonces, la funcion

f(x) = supi∈I

fi(x)

es inferiormente semicontinua.

Demostracion. Sea x ∈ X y xkk∈N un sucesion de puntos que converge a x. Note que para

todo i ∈ I, al tenerse que fi es una funcion inferiormente semicontinua, se cumple que

fi(x) ≤ lım infk→∞

fi(xk).

Tomando el supremo sobre I a ambos lados de la desigualdad, se tiene que

supi∈I

fi(x) ≤ supi∈I

lım infk→∞

fi(xk). (2-1)

Por otro lado, sea n ∈ N+. Entonces, para todo k ≥ n, i ∈ I se cumple que

fi(xk) ≤ supi∈I

fi(xk).

Tomando el ınfimo sobre el conjunto k ≥ n a ambos lados de la desigualdad se tiene que

ınfk≥n

fi(xk) ≤ ınfk≥n

supi∈I

fi(xk).

Tomando el supremo sobre el conjunto n ≥ 0 a ambos lados de la desigualdad se tiene que

lım infk→∞

fi(xk) = supn≥0

ınfk≥n

fi(xk) ≤ supn≥0

ınfk≥n

supi∈I

fi(xk)

= lım infk→∞

supi∈I

fi(xk) = lım infk→∞

f(xk).(2-2)

Combinando las desigualdades (2-1), (2-2) se obtiene que

f(x) ≤ lım infk→∞

f(xk),

con lo cual se sigue el resultado.

8 2 Preliminares

Observacion 2.3. Note que la proposicon 2.6 es analoga a que si la familia fii∈I es

superiormente semicontinua entonces la funcion definida por

f(x) = ınfi∈I

fi(x)

es una funcion superiormente semicontinua.

3. Procesos de decision de

Markov(MDP)

El presente capıtulo introduce los procesos de decision de Markov, a partir de lo expuesto

en [6].Los procesos de decision de Markov modelan la toma de decisiones secuenciales de un

agente bajo condiciones inciertas. Estos se componen de cinco elementos: epocas de decision,

estados, acciones, probabilidades de transicion y recompensas. Cada elemento se describe a

continuacion, para luego dar una definicion formal de un proceso de decision de Markov

3.1. Epocas de decision

El conjuntgo de las epocas de decision es un conjunto T ⊂ R+ que se piensa los tiempos

en los cuales ocurre la toma de decisiones. Este conjunto puede ser discreto o un continuo,

al igual que un conjunto finito o infinito.

Los perıodos o etapas son el tiempo que transcurre entre epocas de decision en problemas

de tiempo discreto.

Si T es un conjunto discreto y |T | = N < ∞ se denomina un problema de horizonte

finito. En caso contrario, se denomina un problema de horizonte infinito.1

Observacion 3.1. Por convencion, en problemas de horizonte finito, no se toman decisiones

en la epoca de decision N , sino que dicha epoca se incluye unicamente para evaluar el estado

final del sistema.

3.2. Conjunto de estados y acciones

Sea S el conjunto de estados posibles del sistema. Ası mismo, considere el conjunto St co-

mo el conjunto de todos los estados posibles en el tiempo t, para el cual se cumple que St ⊆ S.

Sea As el conjunto de acciones disponibles para el agente al estar en el estado s. Sea

A :=⋃s∈S

As el conjunto de acciones disponibles para el agente.

1Para este trabajo, solo se consideran MDPs de horizonte finito.

10 3 Procesos de decision de Markov(MDP)

Observacion 3.2. En este caso, se asume que S, As no varıan con t ∈ T . Para el desarrollo

de este trabajo se asume que S y As son conjuntos discretos y finitos.

Una accion a es escogida aleatoriamente si existe una distribucion de probabilidad

q(·) ∈ P(A)2 tal que la probabilidad de escoger la accion a esta dada por q(a).

Observacion 3.3. Las acciones pueden tomarse de manera aleatoria o determinıstica. En

este caso, una accion determinıstica corresponde a una distribucion de probabilidad degene-

rada. Es decir, la probabilidad de tomar una accion determinıstica es igual a 1.

3.3. Recompensas y probabilidades de transicion

Definicion 3.1. Una funcion de recompensa es una funcion rt : S × As → R tal que

r(s, a) representa la recompensa recibida por el agente al estar en el estado s en el tiempo

t y tomar la accion a. En algunas ocasiones, la funcion de recompensa puede ser definida

como rt : S × As × S → R en donde rt(s, a, j) representa la recompensa obtenida por estar

en el estado s en el tiempo t, tomar la accion a y llegar al estado j.

Definicion 3.2. Una probabilidad de transicion es una distribucion de probabilidad

pt(·, s, a) ∈ P(S) tal que pt(j, s, a) = pt(j|s, a) representa la probabilidad de llegar al estado

j dado que se esta en el estado s en el tiempo t y se toma la accion a.

Observacion 3.4. Dado que en los MDPs de horizonte finito no se toma una decision en la

ultima epoca, la recompensa para t = N esta dada por una funcion rt : S → R donde rN(s)

representa la recompensa recibida dado que el estado final del sistema es s.

3.4. MDP

Definicion 3.3. La tupla T,S,A, pt(·|s, a), rt(s, a) es un proceso de decision de Mar-

kov (MDP).

3.5. Reglas de decision markovianas

Definicion 3.4. Una regla de decision markoviana determinıstica es una aplicacion dt : S→A en donde, ∀s ∈ S dt(s) ∈ As. Se entiende que dt(s) es la accion tomada dado que se esta

en el estado s en el tiempo t. Sea DMDt el conjunto de todas las polıticas markovianas deter-

minısticas en el tiempo t y DMD =⋃t∈T

DMDt el conjunto de todas las polıticas markovianas

determinısticas del MDP.

2P(X) es la coleccion de distribuciones de probabilidad sobre subconjuntos borelianos de X

3.6 Polıticas markovianas 11

Definicion 3.5. Una regla de decision markoviana aleatoria es una aplicacion dt : S →P(A), se tiene que ∀s ∈ S dt(s) = q(·) ∈ P(As). Es decir, la regla determina un distribucion

de probabilidad sobre el conjunto de acciones As dado que se esta en el estado s en el tiempo

t. La distribucion de probabilidad definida esta dada por qdt(s)(·). Sea DMAt el conjunto de

todas las polıticas markovianas aleatorias en el tiempo t DMA =⋃t∈T

DMAt el conjunto de todas

las polıticas markovianas aleatorias del MDP.

3.6. Polıticas markovianas

Definicion 3.6. La tupla π = (d1, d2, . . . , dN−1) es una polıtica markoviana, si para todo

t dt ∈ DMAt o dt ∈ DMD

t . Es decir, en el tiempo t se utiliza la regla de decision dt. Sea

ΠK = DK1 × · · · ×DK

N−1 el conjunto de polıticas del tipo K, donde K es MA si son polıticas

markovianas aleatorias o MD si son polıticas markovianas determinısticas.

Definicion 3.7. Una polıtica estacionaria es aquella polıtica π tal que para ∀i di = d

para algun d ∈ DK, donde K se define como en la definicion 3.6

3.7. Procesos estocasticos inducidos

Para construir un modelo de probabilidad, se considera el siguiente conjunto para el caso de

horizonte finito

Ω = S× AN−1 × S.

Note que como S y A son conjuntos finitos, entonces Ω es un conjunto finito. Sea B(Ω) el

conjunto de conjuntos borelianos sobre Ω, que al ser un conjunto finito es el conjunto de

subconjuntos de Ω. Un elemento ω ∈ Ω es de la forma

ω = (s1, a1, s2, a2, . . . , aN−1, sN).

Note que ω describe los estados ocupados por el sistema y las acciones tomadas en cada una

de las epocas de decision y recibe el nombre de camino de muestreo. Para toda epoca de

decision t se definen las variables aleatorias Xt : Ω→ S, Yt : Ω→ A respectivamente por

Xt(ω) = st y Yt(ω) = at.

Ası mismo, se define la historia del proceso Zt para la epoca decision t por

Z1(ω) = s1 y Zt(ω) = (s1, a1, . . . , st).

Sea ht = (s1, a1, . . . , st−1, at−1, st) la historia hasta el tiempo t. Sea P1(·) la distribucion de

probabilidad que denota la distribucion inicial de los estados del sistema (i.e el sistema co-

mienza en el estado s con probabilidad P1(s)). Una polıtica markoviana π = (d1, d2, . . . dN−1)


induce una medida de probabilidad P π en el espacio medible (Ω, B(ω)) de la siguiente manera

P πX1 = s = P1(s),

P πYt = a|Zt = ht = P πYt = a|Xt = st = qdt(st)(a),

P πXt+1 = s|Zt = (ht−1, at−1, st), Yt = at = pt(s|st, at).

Luego, la probabilidad de un camino de muestreo ω = (s1, a1, s2, . . . , sN) esta dado por

P π(s1, a1, s2, . . . , sN) = P1(s1)qd1(s1)(a1)p1(s2|s1, a1) · · · p(sN |sN−1, aN−1).

A partir de esto, las probabilidades condicionales se calculan de la siguiente manera:

P π(at, st+1, . . . , sN |s1, a1, . . . , st) =P π(s1, a1, . . . , sN)

P π(s1, a1, . . . , st)

dado que la cantidad del denominador no es cero. En caso contrario, la probabilidad es cero.

3.8. MDPs de horizonte finito

3.8.1. Preliminares

Procesos estocasticos inducidos sobre las recompensas

Definicion 3.8. Sea ht = (s1, a1, s2, as, . . . , st−1, at−1, st) una historia hasta el tiempo t

y sea el conjunto Ht = S×A× S× · · · ×A× S el conjunto de todas las historias de acciones

y estados anteriores al tiempo t. Una regla de decision aleatoria dependiente de la

historia es una aplicacion dt : Ht → P(As).

Sea π(d1, d2, . . . , dN−1) una polıtica aleatoria que depende de la historia (i.e sus reglas depen-

den de la historia y son aleatorias). Esta polıtica induce una medida de probabilidad P π(·)sobre el espacio HN . Para cada hN = (s1, a1, . . . , sn) existe una sucesion correspondiente de

recompensas r1(s1, a1), r2(s2, a2), . . . , rN(sN). Sea Rt = rt(Xt, Yt) la recompensa aleatoria

recibida en el tiempo t < N y RN = rN(XN) la recompensa final. Sea R = (R1, R2, . . . , RN)

una secuencia de recompensas aleatorias y sea R el conjunto de todas las posibles secuencias

aleatorias con valores en R. La polıtica π induce una medida de probabilidad P πR(·) sobre el

espacio medible (R, B(R)) dada por

P πR(ρ1, . . . , ρN) = P π[(s1, a1, . . . , sN) : (r1(s1, a1), . . . , rN(sN)) = (ρ1, . . . , ρN))]

Sea ψ : R → R una funcion de utilidad. Es decir, si ψ(R1) > ψ(R2) se tiene que el agente

que toma decisiones prefiere R1. Si ψ(R1) = ψ(R2), entonces la preferencia del agente es

indiferente ante R1 y R2. Segun esto, la utilidad total esperada por la polıtica π esta dada

por

Eπ(ψ(R)) =∑

(ρ1,...,ρN )∈R

ψ(ρ1, . . . , ρN)P πR(ρ1, . . . , ρN).

3.8 MDPs de horizonte finito 13

Dada una polıtica ν, bajo el criterio de utilidad esperada el agente prefiere la polıtica π sobre

ν si

Eπ(ψ(R)) > Eν(ψ(R)).

En caso de igualdad, las polıticas son equivalentes.

3.8.2. Criterio de recompensa total esperada

Sea vπN(s) la recompensa total esperada sobre el horizonte de decision si la polıtica π es

utilizada y s1 = s. Para una polıtica π aleatoria y dependiente de la historia se tiene que

vπN(s) = EπN−1∑t=1

rt(Xt, Yt) + rN(XN)

.

Note que dada una cadena de recompensas (ρ1, . . . , ρN) ∈ R, la expresion anterior corres-

ponde a la funcion ψ(ρ1, . . . , ρN) =N∑i=1

ρi. Si |rt(s, a)| ≤ M <∞ para (s, a) ∈ S× A, t ≤ N

y S,A discretos, entonces vπN(s) existe y es acotado para toda π aleatoria dependiente de la

historia.

3.8.3. Ecuaciones de optimalidad

El objetivo de la teorıa de procesos de decision de Markov es encontrar una polıtica aleatoria

dependiente de la historia optima π∗ tal que para todo s ∈ S se tenga que

vπ∗

N (s) ≥ vπN(s)

para cualquier polıtica π aleatoria dependiente de la historia.

Definicion 3.9. Sea ΠHA,ΠHD los conjuntos de polıticas aleatorias dependientes de la his-

toria y polıticas determinısticas dependientes de la historia, respectivamente. El valor del

MDP v∗N esta definido por

v∗N(s) = supπ∈ΠHA

vπN(s),

y si existe π ∈ ΠHA tal que se alcanza el supremo, se reemplaza el supremo por el maximo.

Para una polıtica optima π∗ se cumple que

v∗N(s) = vπ∗

N (s).

Sea π = (d1, d2, . . . , dN−1) ∈ ΠHA. Sea uπt : Ht → R la recompensa total esperada por utilizar

la polıtica π en las epocas t, t+1, . . . , N−1. Si la historia en la epoca de decision t es ht ∈ Ht,

se define uπt para t < N por

uπt (ht) = Eπht

N−1∑n=t

rn(Xn, Yn) + rN(XN)

,


donde

Eπht(W (Xt, Yt, . . . , XN)) =∑

W (st, at, . . . , sN)P π(at, st+1, . . . , sN |s1, a1, . . . st)

y la suma varıa sobre (at, st+1, . . . , sN) ∈ A× S× A× · · · × S. Sea uπN(hN) = rN(s) cuando

hN = (hN−1, aN−1, s). Cuando h1 = s, uπ1 (s) = vπN(s). En el caso en que π ∈ ΠHD se tiene

que

uπt (ht) = rt(st, dt(ht)) +∑j∈S

pt(j|st, dt(ht))uπt+1(ht, dt(ht), j).

Si π ∈ ΠHA entonces

uπt (ht) =∑a∈Ast

qdt(ht)(a)

rt(st, a) +

∑j∈S

pt(j|st, a)uπt+1(ht, a, j)

.

Se define

u∗t (ht) = supπ∈ΠHA

uπt (ht).

Las ecuaciones de optimalidad (o ecuaciones de Bellman) estan dadas por

ut(ht) = supa∈Ast

rt(st, a) +

∑j∈S

pt(j|st, a)ut+1(ht, a, j)

(3-1)

para t = 1, . . . , N−1 y ht = (ht−1, at−1, st) ∈ Ht. Para t = N se agrega la siguiente condicion

de frontera

uN(hN) = rN(sN) (3-2)

en donde el supremo es reemplazado en (3-1) por un maximo cuando el supremo es alcanzado.

Un caso particular de esto es cuando Ast es finito.

Las ecuaciones de optimalidad tienen las siguientes propiedades:

Sus soluciones son los retornos optimos del perıodo t en adelante para cada t.

Proveen un metodo para saber si una polıtica es optima. Si la recompensa total espera-

da de la polıtica π del perıodo t en adelante satisface las ecuaciones para t = 1, . . . , N ,

entonces es optima.

Se tienen los siguientes teoremas:

Teorema 3.1 (Teorema 4.3.2 en [6]). Suponga ut es una solucion de (3-1) para t = 1, . . . , N−1 y uN satisface (3-2). Entonces, ut(ht) = u∗t (ht) para todo ht ∈ Ht, t = 1, . . . , N

Demostracion. Se probara por induccion que un(hn) ≥ u∗n(hn) para todo hn ∈ Hn y n =

1, . . . , N . Dado que no se toman decisiones en el perıodo N , uN(hN) = rN(hN) = rN(sN) =

uπN(hN) para todo hN ∈ HN y π ∈ ΠHA. Entonces, uN(hN) = u∗N(hN) para todo hN ∈ HN .


Ahora, suponga por ut(ht) ≥ u∗t (ht) para todo ht ∈ Ht para t = n + 1, . . . , N . Sea π′ =

(d′1, d′2, . . . , d

′N−1) una polıtica arbitraria en ΠHA. Para t = n la ecuacion de optimalidad esta

dada por

un(hn) = supa∈Asn

rt(sn, a) +

∑j∈S

pt(j|sn, a)un+1(hn, a, j)

Luego, por la hipotesis de induccion, la definicion de u∗n+1 y el hecho de que la funcion

pt(·|sn, a) es no negativa, se sigue que

un(hn) ≥ supa∈Asn

rt(sn, a) +

∑j∈S

pt(j|sn, a)u∗n+1(hn, a, j)

≥ supa∈Asn

rt(sn, a) +

∑j∈S

pt(j|sn, a)uπ′

n+1(hn, a, j)

≥∑a∈Asn

qd′n(hn)(a)

rt(sn, a) +

∑j∈S

pt(j|sn, a)uπ′

n+1(hn, a, j)

= uπ

′

n (hn).

Como π′ era una polıtica arbitraria y por la definicion del supremo, se tiene que un(hn) ≥u∗n(hn). Se mostrara que para ε > 0 existe π′ ∈ ΠHD para la cual

uπ′

n (hn) + (N − n)ε ≥ un(hn) (3-3)

para cada hn ∈ Hn y n = 1, . . . , N . Para esto construya π′ = (d1, . . . , dN−1) para satisfacer

rn(sn, dn(hn)) +∑j∈S

pn(j|sn, dn(hn))un+1(sn, dn(hn), j) + ε ≥ un(hn)

esto se puede lograr por la definicion del supremo y la definicion de un(hn). Se probara (3-3)

por induccion. Dado que uπ′N (hN) = rN(hN), el resultado se cumple para t = N . Asuma que

uπ′t (ht) + (N − t)ε ≥ ut(ht) para t = n+ 1, . . . , N . Entonces,

uπ′

n (hn) = rn(sn, dn(hn)) +∑j∈S

pn(j|sn, dn(hn))uπ′

n+1(sn, dn(hn), j)

≥ rn(sn, dn(hn)) +∑j∈S

pn(j|sn, dn(hn))un+1(sn, dn(hn), j)− (N − n− 1)ε

≥ un(hn)− (N − n)ε.

Luego, (3-3) se sigue para n = 1, . . . , N . Luego, existe π′ ∈ ΠHR tal que

u∗n(hn) + (N − n)ε ≥ uπ′

n (hn) + (N − n)ε ≥ un(hn) ≥ u∗n(hn).

Haciendo tender ε a cero, se sigue el resultado.


Teorema 3.2 (Teorema 4.3.3 en [6]). Suponga que u∗t , t = 1, . . . , N son soluciones de las

ecuaciones de optimalidad (3-1) (cambiando el supremo por un maximo) sujeto a la condicion

de frontera (3-2) y la polıtica π∗ = (d∗1, d∗2, . . . , d

∗N−1) ∈ ΠHD cumple que

rt(st, d∗t (ht)) +

∑j∈S

pt(j|, st, d∗t (ht))u∗t+1(ht, d∗t (ht), j)

= maxa∈Ast

rt(st, a) +

∑j∈S

pt(j|, st, a)u∗t+1(ht, a, j)

(3-4)

para t = 1, . . . , N − 1. Entonces,

1. Para todo t = 1, . . . , N,

uπ∗

t (ht) = u∗t (ht), ht ∈ Ht.

2. π∗ es una polıtica optima y

vπ∗

N (s) = v∗N(s), s ∈ S.

Demostracion. Se probara el resultado 1 por induccion. Por definicion, se tiene que

uπ∗

N (hn) = u∗N(hn), hn ∈ Hn

Supongase que el resultado se tiene para t = n+1, . . . , N . Entonces, para hn = (hn−1, d∗n−1(hn−1), sn),

u∗n(hn) = maxa∈As

rn(sn + a) +

∑j∈S

pn(j|sn, a)u∗n+1(hn, a, j)

= rn(sn, d

∗n(hn)) +

∑j∈S

pn(j|sn, d∗n(hn))uπ∗

n+1(hn, d∗n(hn), j)

= uπ∗

n (hn)

Luego, se sigue 1. Utilizando el teorema 3.1 se tiene que uπ∗t (ht) = ut(ht). Por definicion,

para t = 1 se obtiene el resultado 2.

3.8.4. Optimalidad de polıticas markovianas determinısticas

Es posible determinar la optimalidad de las polıticas markovianas determinısticas. Para ello,

considere el siguiente teorema

Teorema 3.3 (Teorema 4.4.1 en [6]). Sea u∗t solucion de las ecuaciones (3-1), (3-2) y suponga

que para todo t y st ∈ S, existe a′ ∈ Ast para el que

rt(st, a′)+

∑j∈S

pt(j|st, a′)u∗t+1(ht, a′, j) = sup

a∈Ast

rt(st, a) +

∑j∈S

pt(j|st, a)u∗t+1(ht, a, j)

(3-5)

para todo ht = (ht−1, at−1, st) ∈ Ht. Entonces, existe una polıtica determinıstica, que depende

de la historia, que es optima.


Se probara por induccion que existe una polıtica optima que es markoviana y determinıstica.

Teorema 3.4. Sea u∗t , t = 1, . . . , N soluciones de las ecuaciones (3-1),(3-2). Entonces,

1. Para cada t = 1, . . . , N, u∗t (ht) depende unicamente de ht a traves de st.

2. Si existe a′ ∈ Ast tal que (3-5) se cumple para todo st ∈ S y t = 1, . . . , N − 1, entonces

existe una polıtica optima que es determinıstica y Markov.

Demostracion. Se probara que (1) se cumple por induccion. Como u∗N(hN) = u∗N(hN−1, aN−1, s) =

rN(s) para todo hN−1 ∈ HN−1 y aN−1 ∈ AsN−1, u∗N(hN) = u∗N(sN). Suponga ahora que (1)

se cumpe para n = t+ 1, . . . , N . Entonces,

u∗t (ht) = supa∈Ast

rt(st, a) +

∑j∈S

pt(j|st, a)u∗t+1(ht, a, j)

,

que por hipotesis de induccion se tiene que

u∗t (ht) = supa∈Ast

rt(st, a) +

∑j∈S

pt(j|st, a)u∗t+1(j)

.

Como la cantidad que esta dentro de los corchetes depende de ht solo a traves de st, (1) se

cumple para todo t.

La parte (2) se sigue ya que para todo t y st ∈ S existe a′ ∈ Ast tal que (3-5) se cumple, en-

tonces, para cada t se puede definir d∗t (st) = a′. Entonces, la polıtica π = (d∗1, d∗2, . . . , d

∗N−1) ∈

ΠMD que satisface

rt(st, d∗t (st)) +

∑j∈S

pt(j|st, d∗t (st))u∗t+1(j) = maxa∈Ast

rt(st, a) +

∑j∈S


(3-6)

Entonces, por la parte (1) y el teorema 3.2, π∗ es una polıtica optima.

Luego, se tiene que

v∗N(s) = supπ∈ΠHA

vπN(s) = supπ∈ΠMD

vπN(s).

Se tiene el siguiente teorema

Teorema 3.5 (Proposicion 4.4.3 en [6]). Suponga que S es finito o contable y que As es

finito para todo s ∈ S. Entonces, existe una polıtica Markoviana que es optima.

Demostracion. Por el teorema 3.4 2 basta mostrar que para todo s ∈ S existe a′ ∈ As tal

que la ecuacion

rt(s, a′) +

∑j∈S

pt(j|st, a′)u∗t+1(j) = supa∈As

rt(s, a) +

∑j∈S

pt(j|s, a)u∗t+1(j)

.


Es claro que, si As es finito, el supremo del lado derecho de la ecuacion corresponde a evaluar

lo que esta dentro de los corchetes una cantidad finita de veces. Por lo tanto, tomando

a′ ∈ arg maxa∈As

rt(s, a) +

∑j∈S

pt(j|s, a)u∗t+1(j)

se cumple la ecuacion deseada y se puede construir la polıtica markoviana optima.

3.8.5. Algoritmo de induccion hacia atras

A continuacion se presenta el algoritmo de induccion hacia atras

1. Sea t = N y

u∗N(sN) = rN(sN) ∀sN ∈ S,

2. Substituya t por t− 1 y compute u∗t (st) para todo st ∈ S por

u∗t (st) = maxa∈Ast

rt(s, a) +

∑j∈S


. (3-7)

Sea

A∗st,t = arg maxa∈Ast

rt(st, a) +

∑j∈S


. (3-8)

3. Si t = 1, pare. En caso contrario, retorne al paso 2.

Se tiene las siguientes propiedades del algoritmo

Teorema 3.6 (Teorema 4.5.1 en [6]). Suponga que u∗t , t = 1, . . . , N y A∗st,t, t = 1, . . . , N − 1

satisfacen (3-7), (3-8). Entonces,

Para t = 1, . . . , N y ht = (ht−1, at−1, st)

u∗t (st) = supπ∈ΠHA

uπt (ht), st ∈ S.

Sea d∗t (s) ∈ A∗st,t para todo st ∈ S, t = 1, . . . , N−1, y sea π∗ = (d∗1, . . . , d∗N−1). Entonces,

π∗ ∈ ΠMD es optima y satisface

vπ∗

N (s) = supπ∈ΠHA

vπN(s), s ∈ S

y

uπ∗

t (st) = u∗t (st), st ∈ S

para t = 1, . . . , N.

4. Optimizacion convexa aplicada a

MDPs distribucionalmente robustos

usando la metrica de Wasserstein

El presente capıtulo toma como referencia los resultados expuestos en [9].

4.1. Robustez distribucional

4.1.1. Notacion

Para el desarrollo del presente capıtulo 4 se considera un MDP de horizonte finito de N

epocas de decision. Se asume que los conjuntos S y As son finitos para todo s ∈ S. Se

considera que P (s′|s, a) es la probabilidad de llegar al estado s′ dado que se esta en el estado

s y se estoma la accion a. Tambien se considera la funcion r : S × A → R, donde r(s, a) es

la recompensa de estar en el estado s y se toma la accion a. Se define la funcion rN : S→ Rtal que q(s) es la recompensa obtenida dado que el estado final del sistema es s. Se asume

que las funciones de recompensas r, rN son funciones acotadas. Para cada s ∈ S se definen

los vectores rs := r(s, a)a∈As ∈ R|As|, ps := P (s′|s, a)s′∈Sa∈As ∈ R|S||As|. El MDP se

asume no estacionario, en el sentido en que por cada vez que un estado s es visitado, se tiene

una realizacion diferente de rs y de ps. El estado en el tiempo t se denota st ∈ S. Dado un

espacio boreliano X, P(X) denota el conjunto de Borel de medidas de probabilidad sobre

X. Sea T := 1, . . . , N −1. Sea ei el i-esimo vector de la base canonica de R|As|. Para t ∈ Tse define vt+1 := vt+1(s)s∈S donde vt+1(s) es el vector de recompensas esperadas para el

tiempo t+ 1. Sea Mm×n(R) el espacio de matrices de tamano m× n con entradas en R. Se

define Vt+1 := [e1v>t+1 · · · e|As|v

>t+1] ∈ M|As|×|S||As|(R). Sean p ∈ M|S||As|×|S|(R), r ∈ M|As|×|S|

las matrices cuya columna s son los vectores ps, rs respectivamente.

4.1.2. Proceso de decision de Markov distribucionalmente robustos

Para el desarrollo del capıtulo 4, se considera un tipo especıfico de MDP en el que las proba-

bilidades de transicion ps y la recompensa rs no se conocen del todo. Sin embargo, se asume

que la distribucion conjunta pertenece a un conjunto de ambiguedad Ds ⊆ P(R|S||As|+|As|)

dado apriori. El objetivo de este tipo de procesos es construir una polıtica que maximice

204 Optimizacion convexa aplicada a MDPs distribucionalmente robustos usando la

metrica de Wasserstein

la recompensa total esperada en el peor de los casos, considerando restricciones sobre la

distribucion de ps y rs especificadas por el conjunto ambiguo Ds. Para esto, se plantea un

juego dinamico de suma cero, en el que el jugador 1 determina la polıtica de control para

maximizar la recompensa, mientras que el jugador 2 escoge la distribucion conjunta µt de

(pst , rst) para minimizar la recompensa total esperada.

Sea ht := (s1, a1, µ1, . . . , st−1, at−1, µt−1, st) la historia hasta la epoca t. Sea Ht el conjunto de

todas las historias hasta la epoca t. Sea Π el conjunto de todas las polıticas de control aleato-

rias dependientes de la historia disponibles para el jugador 1. Si π ∈ Π y π = (π1, . . . , πN−1)

se tiene que πt : Ht → ∆(As). Sea het := (ht, at) la historia extendida hasta la epoca t y el

conjunto Het de todas las historias extendidas hasta la epoca t. El conjunto de estrategias ad-

misibles para el jugador 2 esta definido por Γ := γ := (γ1, . . . , γN−1)|γt : Het → Dst∀t ∈ T .

Dados los parametros (p, r) y el par de estrategias (π, γ) ∈ Π×Γ, se tiene que la recompensa

total esperada esta dada por la expresion

Rs(π, γ) := Eπ,γ[N−1∑t=1

r(st, at) + rN(sN)|s1 = s

],

donde Eπ,γ denota el valor esperado tomado con respecto a la medida probabilidad inducida

por el par de estrategias (π, γ) y s es el estado inicial del sistema. La polıtica de control

optima es la resultante de resolver el juego de suma cero definido por

supπ∈Π

ınfγ∈Γ

Rs(π, γ).

En este contexto, se introduce la funcion vt : S→ R definida por

vt(s) := supπ∈Π

ınfγ∈Γ

Eπ,γ[N−1∑τ=t

r(sτ , aτ ) + rN(sN)|st = s

],

que representa la recompensa esperada en el estado s en la epoca de decision t. Utilizando

los principios de la programacion dinamica de [6] y expuestos en el capıtulo anterior se deriva

la siguiente version de la ecuacion de Bellman para t ∈ T

vt(s) = supπ∈∆(As)

ınfµ∈Ds

∫χs

(rs + Vt+1ps)>πdµ(ps, rs), (4-1)

y para t = N , vN(s) = rN(s). En este caso, la tratabilidad del problema de optimizacion

interior esta sujeta al conjunto ambiguo Ds. Si este es un conjunto infinito dimensional, el

problema se vuelve no tratable.

4.1.3. Conjuntos ambiguos con metrica de Wasserstein

Para el desarrollo de este proyecto, se definira la estructura de Ds a partir del uso de la metrica

de Wasserstein. Sea χs ⊂ R|S||As|+|As|. Para s ∈ S fijo, considerando xs := [p>s , r>s ]> ∈ χs y

4.2 Optimalidad de polıticas Markovianas 21

dada una medida nominal de probabilidad νs ∈ P(χs) y θ > 0 se define el conjunto ambiguo

Ds(νs, θ) := µ ∈ P(χs)|Wp(µ, νs) ≤ θ

como una vecindad (o bola) en la metrica de Wasserstein de radio θ y centrada en la

distribucion νs, donde

Wp(µ, νs)p := mın

κ∈P(χs×χs)

∫χs×χs

d(x, y)pdκ(x, y)|κ(· × χs) = µ(·), κ(χs × ·) = νs(·)

es la metrica de Wasserstein de orden p, con metrica d y p ≥ 1. Para la metrica de Wasserstein

se tiene la siguiente proposicion.

Proposicion 4.1 (Representacion dual de la distancia de Wasserstein, Teorema 5.10 en [7],

Dualidad de Kantorovich).

Wp(µ, νs)p = sup

(ϕ,ψ)∈Φd

∫χs

ϕ(x)dµ(x) +

∫χs

ψ(x)dνs(x)

,

donde

Φd := (ϕ, ψ) ∈ L1(dµ)× L1(dνs)|ϕ(x) + ψ(y) ≤ d(x, y)p∀x, y ∈ χs.

4.2. Optimalidad de polıticas Markovianas

Se probara que un problema MDP distribucionalmente robusto admite una polıtica de control

Markoviana optima. Es decir, que la ecuacion 4-1 alcanza un maximo sobre el simplex de

probabilidad ∆(As).

Teorema 4.1. Para todo (t, s) ∈ T × S, existe una funcion πoptt : S→ ∆(As) tal que

vt(s) = ınfµ∈Ds

∫χs

(rs + Vt+1ps)>πopt

t (s)dµ(ps, rs).

Demostracion. Sea s ∈ S fijo. Considere la funcion Ft : ∆(As)→ R definida por

Ft(π) = ınfµ∈Ds

∫χs

(rs + Vt+1ps)>πdµ(ps, rs).



Note que para π1, π2 ∈ ∆(As), γ ∈ [0, 1], dada la linealidad de la integral se tiene que

Ft(γπ1 + (1− γ)π2) = ınfµ∈Ds

∫χs

(rs + Vt+1ps)>(γπ1 + (1− γ)π2)dµ(ps, rs),

= ınfµ∈Ds

∫χs

(rs + Vt+1ps)>γπ1dµ(ps, rs)

+

∫χs

(rs + Vt+1ps)>(1− γ)π2dµ(ps, rs),

≥ ınfµ∈Ds

∫χs

(rs + Vt+1ps)>γπ1dµ(ps, rs)

+ ınfµ∈Ds

∫χs

(rs + Vt+1ps)>(1− γ)π2dµ(ps, rs),

= γFt(π1) + (1− γ)Ft(π2).

Entonces Ft es una funcion concava. Dado que la funcion de recompensa es una funcion

acotada, al ser vt(s) un valor esperado de funciones acotadas, se tiene que vt(s) <∞. Como

∀π ∈ ∆(As), t ∈ T , s ∈ S se tiene que Ft(π) ≤ vt(s), entonces, Ft es una funcion propia.

Por otro lado, para µ ∈ Ds defina la funcion gµ : R|As| → R de la siguiente manera

gµ(x) =

∫χs

(rs + Vt+1ps)>xdµ(ps, rs).

Note que para t ∈ R, y ∈ R|As| se cumple que, por linealidad de la integral

gµ(tx+ y) =

∫χs

(rs + Vt+1ps)>(tx+ y)dµ(ps, rs)

= t

∫χs

(rs + Vt+1ps)>xdµ(ps, rs) +

∫χs

(rs + Vt+1ps)>ydµ(ps, rs)

= tgµ(x) + gµ(y).

Entonces, para todo µ ∈ Ds la funcion gµ es una funcion lineal. Luego, gµ es continua. De

esta manera, la funcion gµ|∆(As) (i.e la restriccion de gµ a ∆(As)) es una funcion continua.

En particular, gµ|∆(As) es una funcion superiormente semicontinua. Note que

Ft(π) = ınfµ∈Ds

gµ|∆(As)(π).

Entonces, por la proposicion 2.6 se sigue que Ft es una funcion superiormente semiconti-

nua. Luego, por la proposicion 2.4, Ft es una funcion cerrada. De lo anterior, la ecuacion de

Bellman se puede reescribir de la forma vt(s) = supπ∈∆(As) Ft(π). Dado que se esta optimi-

zando una funcion concava cerrada y propia sobre el conjunto convexo y cerrado ∆(As), por

la proposicion 2.5 se tiene que existe π∗ optimo tal que vt(s) = Ft(π∗). Luego, definiendo

πoptt (s) = π∗ se construye la funcion deseada.

4.3 Formulacion convexa usando dualidad de Kantorovich 23

El teorema 4.1 permite construir la polıtica optima Markoviana πopt := (πopt1 , . . . , πopt

N−1). Sin

embargo, este problema es difıcil de resolver, pues consta de un problema de optimizacion

minimax infinito dimensional para cada par (t, s) ∈ T × S.

4.3. Formulacion convexa usando dualidad de Kantorovich

Utilizando la dualidad de Kantorovich, se puede reformular el problema de vt(s) de la si-

guiente manera:

Teorema 4.2. La ecuacion de Bellman asociada con el problema del MDP distribucional-

mente robusto es equivalente a

vt(s) = maxπ∈∆(As),λ≥0

fs(π, λ; vt+1) (4-2)

para (t, s) ∈ T × S con la condicion de finalizacion vT (s) = q(s). donde fs(·, ·; vt+1) :

∆(As)× R+ → R esta definido por

fs(π, λ; vt+1) = −λθp +

∫χs

ınfx∈χs

(λd(x, y)p + (rs + Vt+1ps)

>π)

dνs(y).

En particular, fs es conjuntamente concava con respecto a (π, λ).

Demostracion. La proposicion 4.1 muestra que

Wp(µ, νs)p = sup

ϕ,ψ∈Φd

∫χs

ϕ(x)dµ(x) +

∫χs

ψ(x)dνs(x)

,

donde

Φd := (ϕ, ψ) ∈ L1(dµ)× L1(dνs)|ϕ(x) + ψ(y) ≤ d(x, y)p∀x, y ∈ χs. (4-3)

En particular, para (ϕ, ψ) ∈ Φd se tiene que ∀x, y ∈ χs ψ(y) ≤ d(x, y)p − ϕ(x). Luego,

∀y ∈ χs ψ(y) ≤ ınfx∈χs

d(x, y)p−ϕ(x). A partir de esto, note que para todo (ϕ, ψ) ∈ Φd se tiene

lo siguiente, ∫χs

ϕ(x)dµ(x) +

∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y)dνs(y) ≤ θp

⇒∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y)dνs(y) ≤ θp −∫χs

ϕ(x)dµ(x)

⇒∫χs

ψ(y)dνs(y) ≤ θp −∫χs

ϕ(x)dµ(x)

⇒∫χs

ϕ(x)dµ(x) +

∫χs

ψ(x)dνs(x) ≤ θp

⇒ Wp(µ, νs)p = sup

ϕ,ψ∈Φd

∫χs

ϕ(x)dµ(x) +

∫χs

ψ(x)dνs(x)

≤ θp.

(4-4)



Por otro lado, considere κ ∈ P(χs × χs) tal que κ(· × χS) = µ(·), κ(χS × ·) = νs(·). Si

d(x, y)p ∈ L1(dκ), entonces dx(x, ·) ∈ L1(dνs). Ası mismo, para todo x ∈ χs y ϕ ∈ L1(dµ) al

tenerse que ϕ(x) es una constante, entonces la funcion definida por ψx(y) = ϕ(x) ∈ L1(dνs)

. Entonces, la funcion definida por ψx(y) = d(x, y)p − ϕ(x) ∈ L1(dνs). Luego, la funcion

definida por ψ(y) = ınfx∈χs d(x, y)p − ϕ(x) ∈ L1(νs). Luego, por definicion del ınfimo, se

tiene que

∀x ∈ χs ϕ(x) + ψ(y) = ϕ(x) + ınfx∈χs

d(x, y)p − ϕ(x) ≤ ϕ(x) + d(x, y)p − ϕ(x) = d(x, y)p.

Entonces, para esta ψ especıfica y para toda ϕ ∈ L1(dµ) se sigue que (ϕ, ψ) ∈ Φd. Luego,

por definicion del supremo se tiene que∫χs

ϕ(x)dµ(x) +

∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y) ≤ Wp(µ, νs)p.

Es decir, la bola de la metrica de Wasserstein se puede escribir de la siguiente manera

Ds(νs, θ) =

µ ∈ P(χs)

∣∣∣∣∀ϕ ∈ L1(dµ)

∫χs

ϕ(x)dµ(x) +

∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y) ≤ θp.

Fıjese (t, s) ∈ T × S y recuerde que x = [p>s r>s ]>. Para µ ∈ Ds, λ > 0 y ϕ ∈ L1(dµ) se sigue

que∫χs

ϕ(x)dµ(x) +

∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y) ≤ θp

⇐⇒∫χs

ϕ(x)dµ(x) +

∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y)− θp ≤ 0

⇐⇒ λ

(∫χs

ϕ(x)dµ(x) +

∫χs

ınfx∈χs

(d(x, y)p − ϕ(x)) dνs(y)− θp)≤ 0

⇐⇒∫χs

(rs + Vt+1ps)>πdµ(ps, rs) +

∫χs

λϕ(x)dµ(x) +

∫χs

ınfx∈χs

λd(x, y)p − λϕ(x)dνs(y)− λθp

≤∫χs

(rs + Vt+1ps)>πdµ(ps, rs).

En particular, para todo π ∈ ∆(As)

ınfµ∈Ds

∫χs

(rs+Vt+1ps)>πdµ(ps, rs)+

∫χs

λϕ(x)dµ(x)+

∫χs

ınfx∈χs

λd(x, y)p−λϕ(x)dνs(y)−λθp ≤ Ft(π).

Como Ds ⊆ P(χs) se tiene que,

Ft(π) ≥ ınfµ∈P(χs)

∫χs

(rs+Vt+1ps)>πdµ(ps, rs)+

∫χs

λϕ(x)dµ(x)+

∫χs

ınfx∈χs

λd(x, y)p−λϕ(x)dνs(y)−λθp.

(4-5)

4.3 Formulacion convexa usando dualidad de Kantorovich 25

Luego,

Ft(π) ≥ supλ≥0

ınfµ∈P(χs)

∫χs

(rs + Vt+1ps)>πdµ(ps, rs) +

∫χs

λϕ(x)dµ(x)

+

∫χs

ınfx∈χs

λd(x, y)p − λϕ(x)dνs(y)− λθp. (4-6)

Note que para todo (t, s) ∈ T ×S, π ∈ ∆(As), se tiene que (rs+Vt+1ps)>π ∈ R. En particular,

para λ > 0 y teniendo en cuenta que vt es acotado para todo t se tiene que∫χs

(rs + Vt+1ps)>πdµ(ps, rs) ≤ |As|(K +M)

∫χs

dµ(x) = |As|(K +M) <∞,

donde K,M ∈ R son cotas adecuadas para rs y vt+1. Entonces, ϕ = −1λ

(rs + Vt+1ps)>π ∈

L1(dµ). Con este ϕ, se obtiene en (4-6) que

Ft(π) ≥ supλ>0

fs(π, λ; vt+1).

Note que si λ = 0, fs(π, 0; vt+1) = ınfx∈χs

(rs + Vt+1ps)>π. Entonces, para cualquier x ∈ χs

fs(π, 0; vt+1) = ınfx∈χs

(rs+Vt+1ps)>π ≤ (rs+Vt+1ps)

>π ⇒ fs(π, 0; vt+1) ≤∫χs

(rs+Vt+1ps)>πdµ(x).

Entonces,

Ft(π) ≥ supλ≥0

fs(π, λ; vt+1).

Note que

supλ≥0

fs(π, λ; vt+1) = − ınfλ≥0

λθp −

∫χs

ınfx∈χs


>π)

dνs(y)

. (4-7)

Ası mismo, note que

Ft(π) = − supµ∈Ds

∫χs

−(rs + Vt+1ps)>πdµ(ps, rs). (4-8)

Entonces, se tiene que

supµ∈Ds

∫χs

−(rs+Vt+1ps)>πdµ(ps, rs) ≤ ınf

λ≥0

λθp −

∫χs

ınfx∈χs


>π)

dνs(y)

.

(4-9)

Note que los lados derecho e izquierda de la ecuacion (4-9) coinciden con las definiciones de

vP y vD dados en la proposicion (A.1), tomando Ψ(x) = −(rs + Vt+1ps)>π. Esta funcion es

una funcion acotada. Luego por el teorema (A.1) el problema supλ≥0

fs(π, λ; vt+1) admite una

solucion λ∗ y es equivalente al problema de la izquierda.



Entonces, Ft(π) = supλ≥0

fs(π, λ; vt+1). Por lo tanto,

vt(s) = supπ∈∆(As)

maxλ≥0

fs(π, λ; vt+1).

El teorema 4.1 muestra que existe π∗ ∈ ∆(As) que es optimo para el problema de optimiza-

cion. Entonces,


fs(π, λ; vt+1).

Para mostrar que fs es concava, sean π1, π2 ∈ ∆(As), λ1, λ2 ≥ 0, t ∈ [0, 1]. Sea πt = tπ1 +

(1 − t)π2, λt = tλ1 + (1 − t)λ2. Entonces, πt ∈ ∆(As) al ser un conjunto convexo y λt ≥ 0.

Para ε > 0, se tiene que existe xε ∈ χs tal que

f(πt, λt; vt+1) + ε > −λtθp +

∫χs

λtd(xε, y)p + (rs + Vt+1ps)>πtdνs

= t

(−λ1θ

p +

∫χs

λ1d(xε, y)p + (rs + Vt+1ps)>π1dνs

)+ (1− t)

(−λ2θ

p +

∫χs

λ2d(xε, y)p + (rs + Vt+1ps)>π2dνs

).

(4-10)

Por otro lado, como xε ∈ χs se tiene que para i = 1, 2 se cumple que

f(πi, λi; vt+1) ≤ −λiθp +

∫χs

λid(xε, y)p + (rs + Vt+1ps)>πidνs.

Luego,

fs(πt, λt; vt+1) + ε > tfs(π1, λ1, vt+1) + (1− t)fs(π2, λ2; vt+1)

Haciendo tender ε a cero, se obtiene que fs es conjuntamente concava.

Al utilizar la formulacion resultante del teorema 4.2, se puede resolver el MDP distribucio-

nalmente robusto a traves de programacion convexa finito dimensional. Note que el problema

original infinito dimensional se transfiere a la evaluacion de la funcion fs, que requiere resol-

ver un problema de minimizacion por cada y ∈ χs. En el caso en que se tiene una construccion

orientada a los datos, la distribucion nominal νs es de soporte finito.

4.4. Distribucion nominal con soporte finito

Suponga que a distribucion νs, que es el centro del conjunto Ds tiene soporte finito, xs,1, . . . , xs,M, xs,i :=

[p>s,i r>s,i]> ∈ R|S||As|+|As|, i.e

νs =1

N

M∑i=1

δxs,i , (4-11)

donde la funcion δxs,i(x) es 1 si x = xs,i y cero en caso contrario. Esta construccion corres-

ponde con la distribucion empırica en la que se tienen M observaciones de las probabilidades

y las recompensas. Con esta medida, se obtiene el siguiente resultado:

4.4 Distribucion nominal con soporte finito 27

Corolario 4.1. Con la medida dada por la ecuacion (4-11) se tiene que


1

M

M∑i=1

fs,i(π, λ; vt+1), (4-12)

para (t, s) ∈ T ×S con vN(s) = rN(s), donde para i = 1, . . . ,M, fs,i(·, ·; vt+1) : ∆(As)×R+ →R definida por

fs,i(π, λ; vt+1) := −λθp + ınfx∈χs

(λd(x, xs,i)p + (rs + Vt+1ps)

>π)

Demostracion. Al considerar la ecuacion (4-10) con esta medida, se obtiene que para todo

(t, s) ∈ T × S y i = 1, . . . ,M se tiene que

fs(π, λ; vt+1) = −λθp +1

M

M∑i=1

ınfx∈χs


>π)

=1

M(−Mλθp +

M∑i=1

ınfx∈χs


>π))

=1

M

M∑i=1

−λθp + ınfx∈χs


>π)

=1

M

M∑i=1

fs,i(π, λ; vt+1)

En este caso, para poder evaluar la funcion objetivo en (4-12) se requiere resolver M pro-

blemas de optimizacion convexa. Con esta reformulacion, se ha eliminado el problema infi-

nitodimensional y se hace tratable el problema. Dado que esta nueva funcion es de caracter

aditivo, y que cada funcion f depende unicamente de uno de los datos obtenidos xs,i se

pueden implementar metodos de optimizacion distribuida. Sin embargo, se tiene el siguiente

acercamiento

Corolario 4.2. Con la medida dada por (4-11). La ecuacion de Bellman asociada al MDP

distribucionalmente robusto es equivalente a

vt(s) = maxπ∈∆(As)

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi (4-13)

para (t, s) ∈ T × S con vN(s) = rN(s), donde

Bs :=

(x1, . . . , xM) ∈ χMs

∣∣∣∣∣ 1

M

M∑i=1

d(xi, xs,i)p ≤ θp

Q(vt+1) := [Vt+1 I] ∈M|As|×(|S||As|+|As|)(R)



Demostracion. Dada la utilizacion del ınfimo en la ecuacion (4-12) se tiene que para todo

ε > 0 para i = 1, . . . ,M existe xεi ∈ χs tal que

vt(s) + ε > maxπ∈∆(As),λ≥0

1

M

M∑i=1

π>Q(vt+1)xεi + λ

(−θp +

1

M

M∑i=1

d(xεi , xs,i)p

)

Note que si 1M

M∑i=1

d(xεi , xs,i)p > θp, al tener un problema de maximizacion sobre λ, se puede

tomar λ = ∞, lo que harıa que vt(s) = ∞. Entonces, 1M

M∑i=1

d(xεi , xs,i)p ≤ θp (i.e xεi ∈ Bs).

Luego, por definicion del ınfimo se tiene que

vt(s) + ε > maxπ∈∆(As),λ≥0

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi + λ

(−θp +

1

M

M∑i=1

d(xi, xs,i)p

).

Por el analisis anterior, dado que −θp + 1M

M∑i=1

d(xεi , xs,i)p < 0 al valor maximo sobre λ ocurre

en λ = 0. Entonces,

vt(s) + ε > maxπ∈∆(As)

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi.

Haciendo tender ε a cero, se tiene que

vt(s) ≥ maxπ∈∆(As)

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi.

Por la proposicion 2.3 se sigue que

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi + λ

(1

M

M∑i=1

d(xi, xs,i)p − θp

)

≥ ınfx∈χM

s

1

M

M∑i=1

π>Q(vt+1)xi + λ

(1

M

M∑i=1


)

Tomando el supremo sobre λ en ambos lados de la desigualdad y considerando el analisis

anterior respecto a al valor maximo de λ cuando x ∈ Bs se tiene que

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi = supλ≥0

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi + λ

(1

M

M∑i=1


)

≥ supλ≥0

ınfx∈χM

s

1

M

M∑i=1

π>Q(vt+1)xi + λ

(1

M

M∑i=1


).

4.5 Construccion descentralizada de distribucion en el peor caso 29

Por otro lado, note que

supλ≥0

ınfx∈χM

s

1

M

M∑i=1

π>Q(vt+1)xi + λ

(1

M

M∑i=1


)

= supλ≥0

1

M

M∑i=1

−λθp + ınfx∈χs


>π)

= supλ≥0

1

M

M∑i=1

fs,i(π, λ; vt+1)

Usando la ecuacion (4-12) se tiene que

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi ≥ vt(s).

En particular,

maxπ∈∆(As)

ınfx∈Bs

1

M

M∑i=1

π>Q(vt+1)xi ≥ vt(s).

Luego, se sigue el resultado.

4.5. Construccion descentralizada de distribucion en el

peor caso

Asumiendo que la distribucion nominal es de soporte finito, se puede construir una distribu-

cion para (ps, rs) en el peor caso. Se tiene el siguiente resultado:

Proposicion 4.2. Suponga que la distribucion nominal de νs esta dada por (4-11). Si el

problema de minimizacion de (4-13) admite una solucion optima (x∗1, . . . , x∗M) entonces

µ∗ =1

M

M∑i=1

δx∗i

es una distribucion en el peor caso, donde π∗ es la solucion optima al problema de maximi-

zacion de (4-13).

Demostracion. Dada la definicion de vt(s) dada en (4-1), por el ınfimo sobre µ ∈ Ds se tiene

que para cualquier µ ∈ Ds se cumple que

vt(s) ≤∫χs

[(π∗)>Q(vt+1)x]dµ(x). (4-14)



Usando la dualidad de Kantorovich, se tiene que

Wp(µ∗, νs)

p = supϕ,ψ∈Ψd

1

M

M∑i=1

(ϕ(x∗i ) + ψ(xs,i))

donde el conjunto factible es definido en (4-3). Como ∀(x, y) ∈ χs×χs ϕ(x)+ψ(y) ≤ d(x, y)p

se sigue que

Wp(µ∗, νs)

p ≤ 1

M

M∑i=1

d(x∗i , xs,i)p ≤ θp.

Lo anterior dado que, por la formulacion de vt(s) mostrada en (4-13), x∗ ∈ Bs. Entonces,

µ∗ ∈ Ds. En particular, la ecuacion (4-14) aplica para µ∗. Es decir,

vt(s) ≤∫χs

[(π∗)>Q(vt+1)x]dµ∗(x)

=1

M

M∑i=1

(π∗)>Q(vt+1)x∗i .

Por el corolario 4.2 se tiene que el valor del lado derecho de la desigualdad es precisamente

vt(s), por lo que µ∗ es la distribucion en el peor caso.

5. Aplicacion de MDPs al control de

posicion de un drone de 4 helices

5.1. Modelo del drone

Para el desarrollo de las simulaciones, se hace uso de un drone de 4 helices. Se considera que

el marco movil del drone esta en posicion de X. Esta configuracion es ilustrada en la figura

5-1. Note la definicion de los angulos θ, ϕ, ψ.

Para interes del trabajo, se considera que el control a realizar solo se hara sobre la posicion

Figura 5-1.: Configuracion en X

X-Y del drone. La referencia del controlador de altura se mantiene fija en 3 metros. Las

perturbaciones consideradas dentro del modelo consisten en fuerzas aplicadas al drone, con

respecto al marco de referencia inercial y se consideran que son perturbaciones resultantes

de la accion del viento sobre el cuerpo del drone. Para poder considerar un modelo de toma

de decisiones secuencial, se determina el tiempo tp = 1,2 segundos equivalente al tiempo que

pasa entre etapas de decision. Despues de tp segundos se determina la posicion del drone y

se toma una accion segun lo deseado.

5.1.1. Arquitectura del modelo

La figura 5-2 muestra la arquitectura del controlador.

32 5 Aplicacion de MDPs al control de posicion de un drone de 4 helices

Figura 5-2.: Estructura general del sistema de control

El controlador de alto nivel, al cabo de tp segundos utiliza la posicion actual del drone pa-

ra definir la referencia que deben seguir los controladores PID para lograr el objetivo deseado.

La figura 5-3 muestra el modelo de simulink del simulador del drone utilizado [2].

El simulador esta compuesto por los siguientes bloques:

Figura 5-3.: Modelo de simulink del simulador

1. Controlador de posicion: Este bloque se encarga de controlar la posicion X-Y del

drone segun una referencia dada. Consta dos controladors PID que son utilizados para

determinar los angulos ϕ, θ de referencia. Las constantes del controlador estan dadas

5.1 Modelo del drone 33

por Ki = 0,9, Kd = 0,25, Ki = 0,095 que fueron determinados a partir de sintonizacion

manual. Los controladores tienen una saturacion para los angulos de ±12 grados.

2. Controlador de orientacion: Este bloque se encarga de controlar la orientacion del

drone. Utiliza 4 controladores PID para controlar los angulos θ, ϕ, ψ y la altura Z de

referencia. La tabla 5-1 muestra los valores de los controladores

Variable a controlar Kp Ki Kd

ϕ 2 1.1 1.2

θ 2 1.1 1.2

ψ 4 0.5 3.5

z 2 1.1 3.3

Tabla 5-1.: Tabla de controles

3. Bloque de controles: Este bloque se encarga de hacer la relacion entre los comando

de correccion de angulos y la altura, para determinar las velocidades a la que deben

girar los motores para obtener el efecto deseado.

4. Bloque de dinamicas Es el bloque encargado de simular las dinamicas de los motores

y de simular el sistema dinamico del drone con las perturbaciones consideradas.

5.1.2. Parametros de simulacion

Para simular el drone, se consideran los siguientes parametros fısicos del drone ( (M)=Motor,

(C)= Control electronico de velocidad, (Ce)= Cuerpo central, (B)=Brazos) ).

Parametro Valor Unidad Parametro Valor Unidad

Masa (M) 73 grms Distancia a centro (C) 8.26 cm

Distancia a centro (M) 22.23 cm Masa (Ce) 431 grms

Altura sobre el brazo (M) 3.18 cm Radio (Ce) 5.64 cm

Radio (M) 1.4 cm Altura (Ce) 4.29 cm

Masa (C) 30 grms Masa (B) 45 grms

Ancho (C) 2.54 cm Radio (B) 3.25 cm

Largo (C) 5.71 cm Largo (B) 18.57 cm

Tabla 5-2.: Parametros fısicos del drone

En el caso de las perturbaciones, se asume que la fuerza que imprime el viento sobre viento

se distribuye con una distribucion normal con media µ = 0 y varianza σ2 = 0,04. Para


determinar el valor maximo y mınimo de la perturbacion, se hizo uso de la escala de Beaufort.

La tabla 5-3 muestra la escala de Beaufort.

Velocidad del viento (km/h) Denominacion

0-1 Calma

2-5 Ventolina

6-11 Brisa debil

12-19 Brisa ligera

20-28 Brisa moderada

29-38 Brisa fresca

39-49 Brisa fuerte

50-61 Viento fuerte

62-74 Viento duro

75-88 Temporal fuerte

89-102 Temporal duro

103-117 Temporal muy duro

+118 Temporal huracanado

Tabla 5-3.: Escala de Beaufort

Utilizando la escala se decide que se van a simular vientos de maximo 40 km/h. La relacion

entre velocidad y fuerza aplicada del viento esta dada por la ecuacion:

F =ρ · Cd · V 2 · A

2

donde V es la velocidad del viento en metros por segundo,A el area perpendicular sobre la que

actua el viento en metros cuadrados, Cd el coeficiente de arrastre y ρ la densidad del viento

que es de 1.22 Kg/m3 . Asumiendo que las perturbaciones dadas se dan sobre centro de masa

del drone, que la parte central del mismo se aproxima a una forma cilındrica (determinada

por los parametros dados en la tabla 5-2) y que el viento interactua unicamente con la mitad

del area del cilindro, se obtiene que las fuerzas de las perturbaciones se encuentran dentro

±0,22 Newtons de fuerza. Ası mismo, se considera que durante el tiempo que transcurre

entre toma de decisiones, el viento es constante. Sin embargo, de un perıodo a otro cambia.

5.2. Modelo del controlador

5.2.1. Definicion de estados y acciones

Para definir la cadena de Markov, es necesario definir el conjunto de estados S y el conjunto

de acciones As para todo s ∈ S. Para lograr esto, el semiplano positivo X-Y es dividido en una

5.2 Modelo del controlador 35

Conjunto de estados As

Sld 1, 2, 5, 9Srd 1, 3, 7, 9Slu 2, 4, 6, 9Sru 3, 4, 8, 9Su 2, 3, 4, 6, 8, 9Sl 1, 2, 4, 5, 6, 9Sd 1, 2, 3, 5, 7, 9Sr 1, 3, 4, 7, 8, 9Sin 1, 2, 3, 4, 5, 6, 7, 8, 9

Tabla 5-4.: Acciones segun estado

grilla. La longitud del lado de los cuadrados que componen la grilla se fija en 0.1 metros. El

centro de cada cuadrado se localiza en los multiplos de 0.1 en ambas coordenadas (i.e 0, 0.1,

0.2, etc). Considerando una particion de n columnas y m filas, cada uno de los cuadrados

de la grilla son un estado. El estado numero 1 es el cuadrado centrado en el origen. Los

estados son enumerados horizontalmente en orden ascendente. Una vez se llega a la n-esima

columna, la numeracion continua en la fila inmediatamente superior.

Dentro del conjunto S, se definen los siguientes subconjuntos

Sld = S1, Srd = Sn,Slu = S(m−1)·n+1,Sru = SmnSu = S(m−1)·n+j|j = 2, . . . , n− 1Sl = Sj·n+1|j = 2, . . . ,m− 2Sd = Sj|j = 2, . . . , n− 1Sr = Sj·n|j = 2, . . . ,m− 1Sbor = (Su ∪ Sl ∪ Sd ∪ Sr)Sesq = (Sld ∪ Sld ∪ Sld ∪ Sld)Sin = S \ (Sesq ∪ Sbor)

(5-1)

donde Si es el i-esimo estado.

La siguiente convencion es utilizada para las acciones. En este contexto se entiende que la

accion “adelante”significa que el drone debe ir un cuadrado arriba en la grilla. Las acciones

disponibles en cada estado son definidas en la tabla 5-4 para cada s en el conjunto de es-

tados. La Figura 5-4 ilustra la numeracion del conjunto de estados S para el caso n = 4 y

m = 3 junto con una identificacion de los subconjuntos definidos en (5-1).


1 2 3 4

5 6 7 8

9 10 11 12 Sesq

Sin

Sl

Sr

Sd

Su

Figura 5-4.: Ejemplo de numeracion y de subconjuntos

5.2.2. Definicion de matriz de probabilidad de transicion

Para definir las matriz de probabilidad de transicion, se hace uso de un enfoque frecuencial.

Para esto, se define el tiempo tp como el tiempo entre la toma de decisiones del drone. Luego,

se define el numero de experimentos ne a realizar. Por cada experimento el drone se ubica en

el origen y se le indica que tome cada accion por separado. Tambien, por cada experimento se

tiene valores diferentes para las perturbaciones. Al cabo de tp segundos se observa la posicion

final del drone. De esta manera, se obtiene una estimacion de la probabilidad de que el drone

logre llegar a la posicion deseada despues de tp segundos. Se asume que las probabilidades

son homogeneas, por lo que se tiene la misma matriz de probabilidad de transicion en todo

los estados. Considerando que en los estados de los bordes y las esquinas de la grilla se tiene

que bajo ciertas acciones se sale de esta, se aplica una normalizacion de las probabilidades

para garantizar que estas sumen 1. Para aquellos estados para los cuales no esta disponible

la accion que determina la matriz, la fila correspondiente es de ceros.

5.2.3. Definicion de funciones de recompensa

La funcion de recompensas a utilizar es especificada en el caso de estudio 5.3.

5.2.4. Definicion de polıtica de control

La polıtica de control es la resultante del algoritmo de induccion hacia atras presentado en

la seccion 3.8.5.

5.3. Caso de estudio: Seguimiento de trayectoria con

MDP de horizonte finito

5.3.1. Descripcion

El caso a estudiar es aquel en el que el usuario define un camino que el drone debe seguir.

Sea Sdes ⊂ S el conjunto de estados que forman el camino deseado. Sea M = |Sdes|. Sea

NM := j ∈ N|j ≤ M y sea k : NM → Sdes una funcion tal que k(j) es el estado que se

5.4 Resultados 37

quiere que ocupe el drone en la epoca de decision j. De esta manera, bajo esta consideracion

se define un MDP de horizonte finito con M − 1 epocas de decision.

5.3.2. Funciones de recompensa

Para lograr el objetivo de que el drone siga la trayectoria esperada, se define la siguiente

funcion de recompensa para t = 1, . . . ,M :

rt(s, a) =

1000 si k(t) = s,

0 en caso contrario.

Note que bajo esta definicion, la recompensa depende unicamente del estado y no de las

acciones.

5.4. Resultados

Para el desarrollo de las simulaciones, se considera que el drone se encuentra en el origen

a tres metros de altura y que el tiempo entre epocas de decision es de 1,2 segundos. Se

consideran dos escenarios de prueba. En uno de ellos, el camino escogido comienza en la

posicion inicial del drone. En el otro escenario, el camino no comienza en la posicion inicial

del drone. Las figuras 5-5 y 5-6 muestran los resultados obtenidos.

(a) Posicion del drone (b) Perturbaciones

Figura 5-5.: Resultados camino con misma posicion inicial


(a) Posicion del drone (b) Perturbaciones

Figura 5-6.: Resultados camino con posicion inicial diferente

Se observa que en ambos casos, a pesar de las perturbaciones, el drone es capaz de seguir la

trayectoria dada.

5.4.1. Analisis de sensibilidad ante la matriz de perturbaciones

Para entender la sensibilidad de la polıtica de control frente a la matriz de probabilidades de

transicion, se simularon otras 4 matrices de transicion. Para el mismo camino de los 2 esce-

narios presentados anteriormente, se simulan las polıticas obtenidas. La figura 5-7 muestra

los resultados obtenidos.

5.4 Resultados 39

(a) Camino con posicion inicial igual (b) Camino con posicion inicial diferente

Figura 5-7.: Resultados a diferente matrices

En los resultados se observa que las lıneas que presentan un comportamiento diferente son

los resultados de la matriz 1 y 2. En el caso de de la figura 5-7.a se observa que la diferencia

entre el la lınea roja y la negra ocurre en el estado 13. Allı, el agente toma la decision de ir

en diagonal, cuando debe ir hacia arriba. Posterior a un analisis, se determina que la proba-

bilidad de llegar al estado 18, desde el estado 13, usando la accion 1 es menor para la matriz

utilizada para la simulacion de la lınea negra. Ası mismo, se destaca que la probabilidad de

llegar al estado 18 desde el estado 13 tomando la accion 5 es mayor en la matriz de la lınea

negra que para la matriz de la lınea roja. El agente, siendo consiente de estas diferencias en

probabilidad, y que en dos epocas de decision debe estar en el estado 19, opta por tomar

la decision 5 en vez de la decision 1, que es la ideal. Paralelamente, en el caso de la lınea

azul, se observa que la diferencia con respecto a la lınea roja ocurre en el estado 1. La matriz

utilizada para la lınea azul evidencia que existe una menor probabilidad de llegar al estado

2 desde el estado 1 tomando la accion 2 con respecto a la matriz de la lınea roja. Ası mismo,

existe una mayor probabilidad de llegar al estado 2 desde el estado 1 tomando la accion 5

con respecto a la matriz de la lınea roja. El agente, siendo consiente que debe estar en el es-

tado 3 en dos epocas de decision posterior, opta por tomar la accion 5 para llegar al estado 3.

Por otro lado, para el caso de los resultados mostrados en la figura 5-7.b se observa que

tanto la lınea negra como la azul difieren de la roja en el estado 13. En dicho estado, la

accion ideal a tomar es la accion 7. Sin tanto para el caso de la lınea azul como de la lınea

negra, la probabilidad de llegar a los estados 17 y 18 desde desde el estado 13 con la accion

7 es menor con respecto a las probabilidades de la lınea roja. En ambos casos, la accion 5

garantiza una mayor probabilidad de llegar al estado 18 con respecto a la accion 1. Esto es

relevante, teniendo en cuenta que en el siguiente momento del tiempo el estado deseado es el


estado 23. Ası mismo, se observa que existe una diferencia entre la lınea azul y la lınea negra

en el estado 19. Esto se debe a que en el estado 19, para la lınea negra es menos probable con

respecto a la lınea azul el llegar al estado 24 tomando las acciones 7 y 2 consecutivamente,

que tomar la accion 1 y luego quedarse quieto. Lo anterior, ya que las acciones 7 y 2 son

menos probables de ser efectivas para la lınea negra con respecto a la lınea azul.

5.4.2. Analisis de sensibilidad ante el tipo de perturbacion

Para entender la sensibilidad de la polıtica de control frente al tipo de viento utilizado, se

hizo un cambio en la distribucion de la intensidad de las perturbaciones. En este caso, se

considera una distribucion Beta con parametros α = 2, β = 5. Considerando los mismos

caminos para ambos escenarios la figura 5-8 muestra los resultados obtenidos.

(a) Camino con posicion inicial igual (b) Camino con posicion inicial diferente

Figura 5-8.: Resultados con distintos tipo de viento

Note que al considerar una distribucion Beta, se esta asumiendo que el vector de fuerza del

viento solo toma componentes positivas en X-Y, por lo tanto, habra una tendencia del drone

de irse en la aquellas direcciones (i.e hacia la derecha y hacia arriba). A pesar de esto, la

polıtica no cambia, por lo que se obtienen caminos que siguen las trayectorias dadas. Sin

embargo, no que los resultados de los experimentos con la nueva distribucion (negro, azul,

azul claro) estan desfasados ligeramente hacia arriba y hacia a la derecha con respecto a la

lınea roja, lo que evidencia el efecto del cambio en la distribucion de la fuerza del viento.

6. Conclusiones y trabajo futuro

6.1. Conclusiones

A partir del trabajo realizado, se estudio el concepto de los procesos de decision de Markov.

En este estudio se requirio la comprension de los elementos basicos de la teorıa de los MDPs

de horizonte finito y como estos pueden ser aplicados en distintos contextos. Para ello, se

estudio la aplicacion de los MDPs en el contexto de un problema de control de posicion de un

drone de 4 helices. Se observo que utilizando un modelo de MDP de horizonte finito, junto

con la adecuada estructuracion de la funcion de recompensas, al igual que con la escogencia

de los estados y acciones correspondientes, se puede estructurar una estrategia de control

de alto nivel que garantiza el control de posicion del drone para poder seguir la trayectoria

deseada.

Paralelamente, se logro comprender la formulacion de un MDP en un contexto robusto,

utilizando la metrica de Wasserstein. Se ahondo en el concepto de semi continuidad de

funciones y se comprendio la formulacion dual del problema, para garantizar su tratabilidad.

6.2. Trabajo futuro

Los resultados expuestos en la seccion 5.4 evidencian que al momento de hacer suposiciones

sobre la distribucion de probabilidad que rige la transicion entre estados, existe la posibilidad

de que hayan sesgos que alteran el funcionamiento del controlador. De aquı, para trabajos

futuros se considera la implementacion de algoritmos que permiten aplicar los resultados

del capıtulo 4 al caso de seguimiento de trayectorias en un drone de 4 helices. Para esto, se

podrıa utilizar la suposicion de que la fuerza del viento se distribuye normalmente con media

0 y de varianza desconocida. Para tomar las muestras a utilizar, se puede implementar el

algoritmo actual para determinar las matrices de transicion. Sin embargo, por cada iteracion

del algoritmo, se escoge una varianza diferente. De esta manera, se estarıan obteniendo

muestras que serviran como punto de partida para resolver los problemas de optimizacion

planteados en el capıtulo 4. A partir de los matrices muestreadas, se considera el problema

de optimizacion definido en (4-13). Considerando d como la norma l1 y tomando p = 1 el

problema de optimizacion interior se vuelve un problema lineal. Ası, para un π fijo, se puede

obtener su problema dual. De esta manera, el problema equivalente es de la la forma

maxx∈X

maxu∈U

f(x, u),

42 6 Conclusiones y trabajo futuro

donde los conjuntos X,U corresponden a las restricciones del problema dual. Aquı, serıa

posible utilizar algoritmos de optimizacion para encontrar las soluciones del problema dual,

y a ası, obtener las soluciones del problema primal.

A. Optimizacion estocastica

distribucionalmente robusta usando la


Este apendice presenta los resultados de dualidad fuerte mostrados en [3], considerando

la definicion de la metrica de Wasserstein y la dualidad de Kantorovich presentados en la

seccion 4.1.3.

Considerese una funcion objetivo Ψ : X×Θ→ R y un agente que toma decisiones. El agente

busca tomar la decision x ∈ X con respecto a la funcion objetivo. Sin embargo, al momento

de tomar la decision, la funcion objetivo depende de un parametro ζ ∈ Θ desconocido para

el agente. Es razonable asumir que ζ es un elemento aleatorio con distribucion µ soportada

sobre Θ. En ese caso, se puede formular un problema de optimizacion estocastica de la forma

ınfx∈X

Eµ[Ψ(x, ζ)].

Dado que en la practica el conocimiento de la distribucion que rige el parametro es difıcil

de tener, se considera el problema de optimizacion estocastica distribucionalmente robusto

dado por

ınfx∈X

supµ∈M

Eµ[Ψ(x, ζ)],

en donde el conjunto M es un conjunto de distribuciones de probabilidad definido bajo

ciertas caracterısticas (i.e metricas estadısticas, momentos, etc). En este caso, se estudia el

caso en el que M esta dado por una bola en la metrica de Wasserstein. Se quiere estudiar el

concepto de dualidad, con el fin de hacer tratable el siguiente problema

supµ∈M

Eµ[Ψ(x, ζ)]. (A-1)

Para ello, considere la siguiente proposicion

Proposicion A.1. Sea el problema de optimizacion dado por (A-1). Suponga que la funcion

Ψ es acotada. El valor primal esta dado por

vP := supµ∈P(θ)

∫Θ

Ψ(ζ)µ(dζ)∣∣W p

p (µ, ν) ≤ θp

44A Optimizacion estocastica distribucionalmente robusta usando la metrica de

Wasserstein

y el valor dual esta dado por

vD := ınfλ≥0

λθp −

∫Θ

ınfζ∈Θλd(ζ, γ)−Ψ(ζ) ν(dγ)

.

Entonces, vP ≤ vD.

Observacion A.1. Note que se ha eliminado la dependencia en Ψ de x.

Demostracion. Note que para µ ∈M se tiene que W pp (µ, ν) ≤ θp. Entonces, θp−W p

p (µ, ν) ≥0. Considere el problema de optimizacion dado por

ınfλ≥0

∫Θ

Ψ(ζ)µ(dζ) + λ(θp −W pp (µ, ν)).

Si µ ∈M el optimo ocurre en λ = 0, pues θp −W pp (µ, ν) ≥ 0. En particular,

vP = supµ∈M

∫Θ

Ψ(ζ)(dζ) = supµ∈P(Θ)

ınfλ≥0

∫Θ

Ψ(ζ)µ(dζ) + λ(θp −W pp (µ, ν)).

Escribiendo el Lagrangiano y aplicando la desigualdad minimax se tiene que

supµ∈P(Θ)

ınfλ≥0

∫Θ

Ψ(ζ)µ(dζ)+λ(θp−W pp (µ, ν)) ≤ ınf

λ≥0

λθp + sup

µ∈P(Θ)

∫Θ

Ψ(ζ)µ(dζ)− λW pp (µ, ν)

.

Note que, por la dualidad de Kantorovich y las equivalencias expuestas en (4-4) se tiene que

para u ∈ L1(µ) se cumple que

supµ∈P(Θ)

∫Θ


≤ sup

µ∈P(Θ)

∫Θ

Ψ(ζ)µ(dζ)

−λ(∫

Θ

u(ζ)µ(dζ)−∫

Θ

ınfζ∈Θdp(ζ, γ)− u(ζ) ν(dγ)

)Como Ψ es acotada, para λ > 0 se tiene que u = Ψ/λ ∈ L1(µ). Reemplazando dicha u se

obtiene que

supµ∈P(Θ)

∫Θ


≤ −

∫Θ

ınfζ∈Θλdp(ζ, γ)−Ψ(ζ) ν(dγ).

En particular,

vP ≤ ınfλ≥0

λθP −

∫Θ

ınfζ∈Θλdp(ζ, γ)−Ψ(ζ) ν(dγ)

=: vD

Teorema A.1 (Teorema 1 en [3]). El problema vD admite un minimizador λ∗ y vP = vD.

Bibliografıa

[1] Bertsekas, D.P.: Convex optimization theory. Athena Scientific, Belmont, Massachu-

setts, 2009. – ISBN 9781886529311

[2] D.Hartman, K.Landis, M.Mehrer, S.Moreno, J. Kim: Quadcopter Dynamic

Modeling and Simulation (Quad-Sim). Disponible en https://github.com/dch33/

Quad-Sim. 2014. – Version 1.0

[3] Gao, Rui ; J. Kleywegt, Anton: Distributionally Robust Stochastic Optimization

with Wasserstein Distance. (2016), 04

[4] Goyal, Vineet ; Grand-Clement, Julien: Robust Markov Decision Process: Beyond

Rectangularity. (2018), 11

[5] Mannor, Shie ; Mebel, Ofir ; Xu, Huan: Robust MDPs with k -Rectangular Uncer-

tainty. En: Mathematics of Operations Research 41 (2016), 11, p. 1484–1509

[6] Puterman, Martin L.: Markov decision processes: discrete stochastic dynamic program-

ming. 1. Wiley-Interscience, 1994 (Wiley Series in Probability and Statistics). – ISBN

0471619779,9780471619772

[7] Villani, C: Optimal transport – Old and new. Vol. 338. 2008. – xxii+973 p.

[8] Wiesemann, Wolfram ; Kuhn, Daniel ; Rustem, Berc: Robust Markov Decision Pro-

cesses / COMISEF. 2010 ( 034). – Working Papers

[9] Yang, Insoon: A Convex Optimization Approach to Distributionally Robust Markov

Decision Processes With Wasserstein Distance. En: IEEE Control Systems Letters 1

(2017), p. 164–169

Documents

Cadenas de Markov controladas: Robustez distribucional y