Risk-Averse Planning Under Uncertainty
Mohamadreza Ahmadi Masahiro Ono Michel D. Ingham Richard M. Murray Aaron D. Ames


Region-wise Generative Adversarial Image Inpainting for Large Missing Areas
    
Yuqing Ma, Xianglong Liu, Shihao Bai, Lei Wang, Aishan Liu, Dacheng Tao, Edwin Hancock

Y. Ma, X. Liu, S. Bai, L. Wang, and A. Liu are with the State Key Lab of Software Development Environment, Beihang University, Beijing 100191, China. X. Liu is also with Beijing Advanced Innovation Center for Big Data-Based Precision Medicine (Corresponding author: Xianglong Liu, xlliu@nlsde.buaa.edu.cn)
D. Tao is with the UBTECH Sydney Artificial Intelligence Centre and the School of Information Technologies, Faculty of Engineering and Information Technologies, The University of Sydney, Darlington, NSW 2008, Australia
E. Hancock is with the Department of Computer Science, University of York, York, U.K.

    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




We consider the problem of designing policies for partially observable Markov decision processes (POMDPs) with dynamic coherent risk objectives. Synthesizing risk-averse optimal policies for POMDPs  requires infinite memory and thus undecidable. To overcome this difficulty, we propose a method based on bounded policy iteration for designing stochastic but finite state (memory) controllers, which takes advantage of standard convex optimization methods. Given a memory budget and optimality criterion,  the proposed method modifies the stochastic finite state controller leading to sub-optimal solutions with lower coherent risk.




§ INTRODUCTION


With the rise of autonomous systems being deployed in real-world settings, the associated risk that stems from unknown and unforeseen circumstances is correspondingly on the rise. In particular, in safety-critical scenarios, such as aerospace applications, decision making should account for risk. For example, spacecraft control technology relies heavily on a relatively large and highly skilled mission operations
team that generates detailed time-ordered and event-driven sequences of commands. This approach will
not be viable in the future with increasing number of missions and a desire to limit the operations team
and Deep Space Network (DSN) costs. Future spaceflight missions will be at large distances and light-
time delays from Earth, requiring novel capabilities for astronaut crews and ground operators to manage
spacecraft consumables such as power, water, propellant, and life support systems to prevent mission failure.
In order to maximize the science returns under these conditions, the ability to deal with emergencies and
safely explore remote regions are becoming more and more important <cit.>. Even in Mars rover navigation problems, finding planning policies that minimize risk is of utmost importance due to the uncertainties present in Mars surface data <cit.> as illustrated in Figure 1.

Risk can be quantified in numerous ways. For example, mission risks can be mathematically characterized in terms of chance constraints <cit.>. The preference of one risk measure over
another depends on factors such as sensitivity to rare events, ease of estimation from data, and computational tractability. Artzner et. al. <cit.> characterized a set of natural properties that are desirable for a risk measure, called a coherent risk measure, and  have henceforth obtained widespread
acceptance in finance and operations research, among others. An important example of a coherent risk measure is the conditional value-at-risk (CVaR) that has received significant attention in decision making problems such as Markov decision processes (MDPs) <cit.>. General coherent risk measures for MDPs were studied in <cit.>, wherein it was further assumed the risk measure is time consistent, similar to the dynamic programming property. Following the footsteps of the latter contribution,  <cit.> proposed a sampling-based algorithm for MDPs with static and dynamic coherent risk measures using policy gradient and actor-critic methods, respectively (also, see a model predictive control technique for linear dynamical systems with coherent risk objectives <cit.>). 


However, in many aerospace applications, sensing constraints does not allow for full-state observation and decision making involves partial observation <cit.>. These problems can be represented as a partially observable Markov decision process (POMDP), where decision making is subject to uncertainty stemming from stochastic outcomes as well as partial observation <cit.>. In this paper, we propose a method based on bounded policy iteration to design sub-optimal risk-averse policies for POMDPs. To this end, we first discuss that the problem of designing risk-averse optimal policies is undecidable in general.  Then, we show that a stochastic but finite-memory controller can be synthesized to upper-bound the dynamic risk. Given a memory budget, we propose a policy iteration method to synthesize these finite-state controllers that can increase the number of memory states to improve risk-aversity. We illustrate our proposed method with a numerical example of path planning under uncertainty.

The rest of the paper is organized as follows. The next section reviews some preliminary notions and definitions used in the sequel. In Section <ref>, we discuss POMDPs with coherent risk measures. In Section <ref>, we propose sub-optimal stochastic finite state controllers that minimize the upper-bound on the coherent risk. In Section <ref>, a bounded policy iteration algorithm is formulated to design risk-averse stochastic finite controllers. In Section <ref>, we elucidate our results with a numerical example. Finally, in Section <ref>, we conclude the paper and give directions for future research.



§ PRELIMINARIES


In this section, we briefly review some notions and definitions used throughout the paper.



 §.§ Markov Chains








A Markov chain ℳ is composed of the state space
𝒮, the transition probability defined as the conditional distribution T(.|s):𝒮→ [0,1] such that ∑_s'∈𝒮T(s'|s)=1, ∀ s∈𝒮,
and the initial distribution ι_init such that ∑_s∈𝒮ι_init(s) = 1. An infinite path, denoted by the superscript ω, of the Markov chain ℳ is a sequence of states π = s_0s_1…∈𝒮^ω such that T(s_t+1|s_t)>0 for all t and ι_init(s_0)>0. The probability space over such paths is the defined as follows. The sample space Ω is the set of infinite paths with initial state s ∈𝒮, i.e., Ω = Paths(s). Σ_Paths(s) is the least σ-algebra on Paths(s) containing Cyl(ω), where Cyl(ω)={ω' ∈Paths(s) |ω is a prefix of ω'} is the cylinder set. Finally, in order to specify the probability measure over all  sets of events in Σ_Paths(s), it is sufficient to provide the probability of each cylinder set, which can be computed as
 Pr_ℳ[Cyl(s_0… s_n) ]=ι_init(s_0) ∏_0 ≤ t ≤ nT(s_t+1| s_t). 
Once the probability measure is defined over the cylinder sets, the expectation operator 𝔼_ℳ is also uniquely defined. In the sequel, we remove the subscript whenever the Markov chain is clear from the context.























 §.§ Partially Observable Markov Decision Process
 

  
A POMDP, 𝒫ℳ, consists of:


  * States 𝒮  =
{s_1 ,…,s_|𝒮|} of the
autonomous agent(s) and world model,

  * Actions Act = {α_1,…,α_|Act|} available to the robot,

  * Observations 𝒪 = {o_1,…,o_|𝒪|},


  * A Transition function T(s_j |s_i ,α),

  * A cost, c(s_i,α_i ) ≥ 0, for each state s_i∈𝒮 and action α_i ∈Act.






This paper considers finite POMDPs where 𝒮, Act, and 𝒪
are finite sets. For each action the probability of making a transition from state s_i∈𝒮 to state s_j∈𝒮 under action α∈ Act is given by
T(s_j |s_i ,α). For each state s_i, an observation o ∈𝒪 is generated independently with probability O(o|s_i ). The starting world
state is given by the distribution ι_init(s_i ). The probabilistic components of a
POMDP model must satisfy the following:

    ∑_s  ∈𝒮 T(s |s_i ,α) = 1,    ∀ s_i  ∈𝒮 ,α∈ Act 
    ∑_o ∈𝒪 O(o|s ) = 1,    ∀ s  ∈𝒮
    ∑_s  ∈𝒮ι_init(s ) = 1.









































Given a POMDP, we can define beliefs or distributions over states at each time step to keep track of sufficient statistics with finite description <cit.>. The beliefs b ∈Δ(𝒮), with Δ(𝒮) being the set of probability distributions over 𝒮, for all s ∈𝒮 can be computed using the Bayes' law as follows:

    b_0(s)    = ι_init(s)O(o_0| s)/∑_o ∈ Oι_init(s) O(o | s),
    
        b_t(s)    = O(o_t | s,α_t)∑_s' ∈𝒮 T(s | s',α_t)b_N-1(s')/∑_s ∈𝒮 O(o_t | s,α_t)∑_s' ∈𝒮 T(s | s',α_t)b_N-1(s'),

for all t≥ 1. It is also worth mentioning that (<ref>) is referred to as the belief update equation.



 §.§ Stochastic Finite State Control of POMDPs
 







It is well established that designing optimal policies for POMDPs based on the (continuous) belief states require uncountably infinite memory or
internal states <cit.>. This paper focuses on a particular class of POMDP controllers, namely, stochastic finite state
controllers. These controllers lead to a finite state space Markov chain for the closed loop
controlled system.


  
Let 𝒫ℳ be a POMDP with observations 𝒪, actions Act, and initial
distribution ι_init. A stochastic finite state controller  for
𝒫ℳ is given by the tuple 𝒢 = (G,ω,κ) where





  * G = {g_1,g_2,…,g_|G|} is a finite set of internal states (I-states).


  * ω:G ×𝒪→Δ(G × Act) is a function of internal stochastic finite state controller states  g_k and observation o, such that ω(g_k,o) is a probability distribution over G ×
Act. The next internal state and action pair (g_l,α) is chosen by independent sampling of
ω(g_k,o). By abuse of notation, ω(g_l,α|g_k,o) will denote the probability of
transitioning to internal stochastic finite state controller state g_l and taking action α, when the current internal
state is g_k and observation o is received.


  * κ:Δ(𝒮) →Δ(G) chooses the starting internal FSC state g_0, by independent
sampling of κ(ι_init), given initial distribution ι_init of 𝒫ℳ.
κ(g|ι_init) will denote the probability of starting the FSC in internal state g when
the initial POMDP distribution is ι_init.





































Closing the loop around a POMDP with a stochastic finite state controller yields the
following transition system.


  
Let POMDP 𝒫ℳ have state space 𝒮 and let G be the I-states of stochastic finite state controller 
𝒢. The global Markov chain ℳ^𝒫ℳ,𝒢_𝒮×
G (or simply ℳ, where the stochastic finite state controller and the POMDP are clear from the context) with execution σ = {[s_0,g_0],[s_1,g_1],…}, [s_t, g_t] ∈𝒮× G evolves as follows:



  * The probability of initial global state [s_0,g_0] is
  
    ι_init^ℳ([s_0,g_0 ]) 
                = ι_init(s_0)κ(g_0|ι_init).



  * The state transition probability, T^ℳ, is given by
  
    T^ℳ   ([s_t+1,g_t+1] |
                [s_t,g_t] . )  = 
    ∑_o∈𝒪   ∑_α∈ ActO(o|s_t)ω(g_t+1,α |g_t,o)T(s_t+1|s_t,α).







Note that the global Markov chain arising from a finite state space POMDP also has a finite state
space.



 §.§ Coherent Risk Measures





Consider a probability space (Ω, ℱ, P), a filteration ℱ_0 ⊂⋯ℱ_N ⊂ℱ, and an adapted sequence of random variables (stage-wise costs) c_t, t=0,…, N, where N ∈ℕ_≥ 0∪{∞}.

We further define the spaces 𝒞_t = ℒ_p(Ω, ℱ_t, P), p ∈ [0,∞), t=0,…,N and let 𝒞_t:N=𝒞_t×⋯×𝒞_N and 𝒞=𝒞_0×𝒞_1 ×⋯. We further assume that the sequence c ∈𝒞 is almost surely bounded, i.e., 

    max_t essup | c_t(ω) | < ∞.



In order to describe how one can evaluate the risk of subsequence c_t,…, c_N from the perspective of stage t, we require the following definitions.










A mapping ρ_t:N: 𝒞_t:N→𝒞_t, where 0≤ t≤ N, is called a conditional risk measure, if it has the following monoticity property:

    ρ_t:N(c) ≤ρ_t:N(c'),   ∀ c, ∀ c' ∈𝒞_t:N such that c ≤ c',

where the inequalities should be understood componentwise.





A dynamic risk measure is a sequence of conditional risk measures ρ_t:N:𝒞_t:N→𝒞_t, t=0,…,N.



One fundamental property of dynamic risk measures is their consistency over time. That is, if c will be as good as c' from the perspective of some future time θ, and they are identical between time τ and θ, then c should not be worse than c' from the current time's perspective.



A dynamic risk measure {ρ_t:N}_t=0^T is called time-consistent if for all 0≤ t ≤τ < θ≤ T and all sequences Z,W ∈𝒞_t:N the conditions

    c_t =c'_t, t=τ,…,θ-1,  and 
    ρ_θ,T(Z_θ,…,c_t) ≤ρ_θ,T(W_θ,…,c'_t)

imply

    ρ_τ,N(c_τ,…,c_t) ≤ρ_τ,N(c'_τ,…,c'_t).





If a risk measure is time-consistent, we can define the one-step conditional risk measure ρ_t:𝒞_t+1→𝒞_t, t=0,…,N-1 as follows:

    ρ_t(c_t+1) = ρ_t,t+1(0,c_t+1),

and for all t=1,…,N, we obtain:

    ρ_t,N(c_t,…,c_N)= ρ_t (c_t + ρ_t+1 ( c_t+1+ρ_t+2(c_t+2+⋯
    
        +ρ_N-1(c_N-1+ρ_N(c_N) ) ⋯ )) ).

Note that the time-consistent risk measure is completely defined by one-step conditional risk measures ρ_t, t=0,…,N-1 and, in particular, for t=0, (<ref>) define a risk measure of the entire sequence c ∈𝒞_0:N.

At this point, we are ready to define a coherent risk measure. 



We call the one-step conditional risk measures ρ_t: 𝒞_t+1→𝒞_t, t=1,…,N-1 as in (<ref>) a coherent risk measure if it satisfies the following conditions

    
  * Convexity: ρ_t(λ c + (1-λ)c') ≤λρ_t(c)+(1-λ)ρ_t(c'), for all λ∈ (0,1) and all c,c' ∈𝒞_t+1;
    
  * Monotonicity: If c≤ c' then ρ_t(c) ≤ρ_t(c') for all c,c' ∈𝒞_t+1;
    
  * Time Consistency: ρ_t(c+c')=c+ρ_t(c') for all c ∈𝒞_t and c' ∈𝒞_t+1;
    
  * Positive Homogeneity: ρ_t(β c)= βρ_t(c) for all c ∈𝒞_t+1 and β≥ 0.












Henceforth, all the risk measures considered are assumed to be coherent. In this paper, we are interested in the discounted infinite horizon problems. Let γ∈ (0,1) be a given discount factor. For N=0,1,…, we define the functionals 

    ρ^γ_0,N(c_0,…,c_N) = ρ_0,N(c_0,γ c_1,…, γ^Nc_N) 
    
                                          = ρ_0 (c_0 + ρ_1( γ c_1+ρ_2(γ^2c_2+⋯
      +ρ_N-1(γ^N-1c_N-1+ρ_N(γ^Nc_N) ) ⋯ )) ),

which are the same as (<ref>) for t=0, but with discounting γ^t applied to each c_t. Finally, we have total discounted risk functional ξ_γ:𝒞→ℝ defined as 
    ξ_γ(Z) = lim_N →∞ρ^γ_0,N(c_0,…,c_N).
 From <cit.>, we have that ξ_γ is convex, monotone, and positive homogenoeus. 







§ RISK-AVERSE POMDPS
 

Notions of coherent risk and dynamic risk measures discussed in the previous section have been developed and applied in microeconomics and mathematical finance fields in the past two decades <cit.>. Generally speaking, risk-averse decision making is concerned with the behavior of agents, e.g. consumers and investors, who, when exposed to uncertainty, attempt to lower that uncertainty. The agent averts to agree to a situation with an unknown payoff rather than another situation with a more predictable payoff but possibly lower expected payoff. In a Markov decision making setting, the main idea in risk-averse control is to replace the conventional conditional expectation of the cumulative reward or cost objectives with more general risk measures. 

Consider a stationary (policies, transition probabilities, and cost functions do not depend explicitly on time) controlled Markov process {s_t}, t=0,1,…. Each policy π = {π_t}_t=0^∞ leads to a cost sequence c_t=c(s_t,α_t), t=0,1,…. We define the dynamic risk of evaluating the γ-discounted cost of the policy π as

    V_γ(π,s_0) = ξ_γ( c(s_0,α_0),c(s_1,α_1),…),

where ξ_γ is defined in (<ref>). In this work, we are interested in addressing the following problem:



For a given POMDP 𝒫ℳ, a discount factor γ∈ (0,1), and a total risk  functional V_γ as in (<ref>) with {ρ_t}_t=0^∞ being coherent risk measures, compute 

    π^* ∈argmin_π V_γ(π,b_0).





We refer to a controlled Markov process with the “nested” objective (<ref>) a risk-averse Markov process. Many applications such as portfolio allocation problems <cit.> and organ transplant decisions <cit.> require a risk-averse Markov model. It was also previously demonstrated in <cit.> that coherent risk measure objectives can account for  modeling errors and parametric uncertainty in MDPs. 

The main challenge is that at any time t, the value of ρ_t is ℱ_t-measurable and is allowed to depend on the entire history of the process {s_0,s_1,…} and we cannot expect to obtain a Markov optimal policy <cit.>. 









In order to obtain Markov optimal policies, we need to make the following assumption (see <cit.> for more details):



For any function ϕ(s_t,a_t,s_t+1), we have

    ρ_t(ϕ(s_t,a_t,s_t+1)) = R{ϕ(s_t,a_t,·),s_t,p(s_t,a_t) },

where a_t=π(s_t). The function R is called a Markov risk transition mapping.




Note that the Markov risk transition mapping depends on the function ϕ, the states s, and probability vector p(s,a). The dot in ϕ(s_t,a_t, ·) on the right hand side of (<ref>) represents a dummy variable that is integrated/summed out with respect to the s_t-th row of the transition probability matrix p(s_t,a_t). The simplest case of the Markov risk transition mapping is the conditional expectation 𝔼{·| s_t,a_t}, i.e., 

    R{ϕ(s_t,a_t,·),s_t,p(s_t,a_t) } = 𝔼{ϕ(s_t,a_t,s_t+1)| s_t,a_t}
     = ∑_s_t+1ϕ(s_t,a_t,s_t+1) T(s_t+1| s_t,a_t).

If R is a coherent risk measure as described in Definition <ref>, then the Markov policies are sufficient to ensure optimality <cit.>. In particular, for the CVaR risk measure, the Markov risk transition mapping is given by

    R{ϕ, s, p(s,a) }
    = inf_z∈ℝ{ z + 1/α∑_s'(ϕ(s,a,s')-z)_+ T(s'| s,a)        }.


The risk-averse formulation can be extended to POMDPs as follows.  



Consider the POMDP 𝒫ℳ  with the nested risk objective (<ref>) and γ∈ (0,1). Let Assumption <ref> hold, let ρ_t, t=0,1,… be  coherent risk measures as described in Definition <ref>, and suppose c(·,·) be non-negative and upper-bounded. Then, the stationary optimal policy π^* = {π^*_t}_t=0^∞ = {π^*}_t=0^∞ is the solution of the following Bellman's equations


    V_γ(b)    = min_α∈ Act(c(b,α) + γR{ V_γ(b'),b, p(b' | b,α) }), 
    π^*(b)    ∈argmin_α∈ Act(c(b,α) + γR{ V_γ(b'),b, p(b' | b,α) }),


where c(b,α) = ∑_s ∈𝒮 c(s,α)b(s).





Note that a POMDP can be represented as an MDP over the belief states (<ref>). Hence, a POMDP is a controlled Markov process with states b ∈Δ(𝒮), where the controlled belief transition probability is described as

    p(b' | b,α) = ∑_o ∈𝒪 p(b' | b, o, α) p(o | b, α)  
    = ∑_o ∈𝒪δ(b' - O(o | s,α)∑_s' ∈𝒮 T(s | s',α)b(s')/∑_s ∈𝒮 O(o | s,α)∑_s' ∈𝒮 T(s | s',α)b(s'))  
    ×∑_s ∈𝒮 O(o | s,α)∑_s”∈𝒮 T(s | s”,α)b(s”),

with 
    δ(a) =  1     a=0, 
     0    otherwise.
  Then, given that c(·,·) is non-negative and upper-bounded, from <cit.> and <cit.>, we infer that from the Bellman equations (<ref>) we can obtain the optimal policies. 







We can use a method based on policy iteration to solve the dynamic programming equations (<ref>) to design risk-averse optimal policies. To this end, for k=0,1,…, given a stationary Markov policy π^k, we calculate the corresponding value function as


    V^k_γ(b) = c(b,π^k(b)) + γR{ V^k_γ(b), b, p(b'| b, π^k(b)       }.

Then, we compute the next policy π^k+1 as

    π^k+1(b) ∈argmin_π(   c(b, π(b)) + γR{ V^k_γ(b), b, p(b'| b, π(b)       }).



Unfortunately, the problem of designing risk-averse optimal Markovian policies for POMDPs is undecidable in general. This follows from <cit.> by noting that inf_π V_γ = sup_π(-V_γ).





In the subsequent section, we demonstrate that, if instead of considering policies with infinite-memory we search over finite-memory policies, then we can minimize upper-bounds on the total risk cost functional (<ref>). 





















§ RISK-AVERSE STOCHASTIC FINITE STATE CONTROLLERS


Under a stochastic finite state controller, the POMDP is transformed into a Markov chain ℳ^𝒫ℳ×𝒢_𝒮×𝒢 with design probability distributions ω and κ. We define the total risk functional of this parametric Markov chain as

    V_γ(𝒢,ι_init) = ξ_γ( c([s_1,g_1],α_1),c([s_2,g_2],α_2),…),

where α_ts and g_ts are drawn from the probability distribution ω(g_t+1,α_t | g_t,o_t). In this setting, Problem 1 can be expressed as



For a given POMDP 𝒫ℳ, a stochastic finite state controller 𝒢, a discount factor γ∈ (0,1), and a total risk  functional V_γ as in (<ref>) with {ρ_t}_t=1^∞ being coherent risk measures, compute 

    (ω^*,κ^*) ∈argmin_ω,κ V_γ(𝒢,ι_init).





The optimal value of Problem 2 provides an upper-bound to that of Problem 1, since a stochastic finite state controller only contains finite memory states and it can be at best as good as the belief-based optimal policy (with infinite memory). The latter claim can also be shown using <cit.>, which indicates that any improvement in the parameters of a stochastic finite state controller (in the sense of optimizing the value functions) is at most as good as the belief value function.

For POMDPs controlled by stochastic finite state controllers, the dynamic program is developed in the global state space
𝒮× G. The value function is defined over this global state space, and policy
iteration techniques must also be carried out in the global state space. For a given stochastic finite state controller, 𝒢, and the POMDP 𝒫ℳ, the value function V_γ,ℳ([s,g]) is
the discounted dynamic risk measure under 𝒢, and can be computed by solving a set of
 equations:

    V_γ,ℳ([s,g])
     = ∑_α∈ Act∑_g' ∈𝒢, o ∈𝒪ω(g',α| g,o) O(o|g') c([s,g],α) 
    + γR{ V_γ,ℳ([s',g']),[s,g], T^ℳ([s',g'] |
                [s,g] . ) },

where 
    p(α| g) = ∑_g' ∈𝒢, o ∈𝒪ω(g',α| g,o) O(o|g').
 Then, for each s, the optimal value function over the induced Markov Chain ℳ can be computed by taking the minimum of the above equation over all I-states g

    V^*_γ,ℳ(s) := min_g ∈𝒢 V_γ,ℳ([s,g]).

 Since v ↦R(v,·,·) is convex (because R is a coherent risk measure), (<ref>)  can be solved by a convex optimization. 









We end this section by demonstrating that the optimal values obtained using the stochastic finite state controllers upper-bound those of the belief-based (infinite-memory) policy. 



Consider the POMDP 𝒫ℳ and the Markov chain ℳ induced by the stochastic finite state controller 𝒢. Then, for all s ∈𝒮, we have V^*_γ(b(s)) ≤ V^*_γ,ℳ(s).




The value function of the induced Markov chain ℳ satisfies (<ref>) for all [s,g] ∈𝒮×𝒢. For each I-state g, the value function in beliefs can be computed as

    V_γ([b,g]) := ∑_s ∈𝒮 b(s) V_γ,ℳ([s,g]),

and the optimal value function given by

    V^*_γ(b) = min_g ∈𝒢∑_s ∈𝒮 b(s) V_γ,ℳ([s,g]).

Applying Hölder inequality to the right-hand side of the above equality, we obtain

    V_γ^*(b)    ≤min_g ∈ G(sup|∑_s∈𝒮 b(s) | ) |V_γ,ℳ([s,g])| 
       = min_g ∈𝒢 V_γ,ℳ([s,g]),

where in the last inequality we used the fact that ∑_sb(s)=1 since b ∈Δ(𝒮) and the fact that V_γ,ℳ([s,g]) is non-negative (since c is non-negative). From (<ref>), we infer V^*_γ≤ V^*_γ,ℳ.




§ A BOUNDED POLICY ITERATION ALGORITHM FOR RISK-AVERSE STOCHASTIC FINITE STATE CONTROLLERS
 

So far, we showed that  synthesizing an infinite memory controller for POMDPs with coherent risk objectives is undecidable. On the other hand, a stochastic finite state controller can upper-bound the coherent risk  for a POMDP. In this section, we provide a computational method based on bounded policy iteration to design risk-averse stochastic finite state controllers. Furthermore, we propose techniques for minimizing the upper bound on the total coherent risk by adding I-states to the algorithm in order to escape local minima.



Policy iteration incrementally improves a controller by alternating between two steps: Policy Evaluation and Policy Improvement, until convergence to an optimal policy <cit.>.  During policy improvement, a dynamic programming update using the so called dynamic programming backup equation (DP Backup)  is used. For a risk-averse POMDP, the DP Backup is given by

    V_γ(b) =  min_α∈ Act( c(b,α) +γR{ V_γ(b), b, p(b'| b, α) }),

The r.h.s. of the DP Backup  can be applied to any risk value function. The effect is a risk reduction (if possible) at every belief state.  

However, DP Backup is difficult to use directly as it must be computed at each belief state in the belief space, which is uncountably infinite.




In <cit.>, a methodology called the Bounded Policy Iteration is proposed for stochastic finite state controllers, which allows stochastic finite state controllers with fewer I-states to have comparable performance in comparison with deterministic finite state controllers, while allowing the stochastic finite state controller to grow in a bounded fashion – only one (or a few) I-state(s) need to be added at a time to escape a local minima. 

Before  presenting our proposed bounded policy iteration method for risk-averse stochastic finite state controllers, we recall the following important definition.












A belief state b is called a tangent belief state, if V_γ(b) touches the DP Backup of
V_γ(b) from above. Since V_γ(b) must equal V_g^β for some g, we also say
that the I-state g is tangent to the backed up value function V_γ at b.





Equipped with this definition, the two steps involved in our algorithm is described next.



 §.§ I-States Improvement via  Convex Optimization

Let V⃗_γ,ℳ(g) ∈ℝ^|S| denote the vectorized V_ℳ([s,g]) in s. We say that an I-state g is  improved, if the tunable stochastic finite state controller parameters associated with that I-state can be adjusted so that V⃗^*_γ,ℳ(g) decreases. 

As a first step, we point out that the search over κ can be dropped. This is simply because the initial I-state is chosen by computing the best valued I-state for the given initial belief, i.e., κ(g_init)  =  1, where 
    g_init  =  g (ι⃗_init^ℳ)^TV⃗_γ,ℳ(g).





After initialization, we pose the improvement as a convex optimization as follows:

I-state Improvement Convex Optimization:
For the I-state g, the following convex optimization is constructed over the variables ϵ, ω(g',α|g,o), ∀ g',α,o

    ϵ> 0,ω(g',α|g,o)max   ϵ   
       subject to   
       Improvement Constraint:   
       V_γ,ℳ([s,g]) + ϵ≤r.h.s. of (<ref>),  ∀ s ∈𝒮,    
       Probability Constraints:   
       (g',α)∈ G× Act∑ω(g',α| g,o)=1,  ∀ o ∈𝒪,   
       ω(g',α| g, o)≥ 0,  ∀ g'∈ G, α∈ Act, o ∈𝒪.












The above convex optimization searches for ω values that improve the I-state value vector V⃗^*_γ,ℳ(g) by maximizing the decision variable ϵ. If an improvement is found, i.e., ϵ > 0, the parameters of the I-state are updated by the corresponding minimizing ω. 


































































































 















Algorithm <ref> outlines the main steps in the bounded policy iteration for risk-averse stochastic finite state controllers. The algorithm has two distinct parts. First, for fixed  parameters of the stochastic finite state controller (ω), policy evaluation is carried out, in which V_γ,ℳ([s,g]) is computed using the following convex optimization (Steps 2, 10 and 18): For each I-state g, we have the following: 

    ϵ_1> 0,ϵ_2> 0,V_γ,ℳmin   ϵ_1-ϵ_2   
       subject to   
       V_γ,ℳ([s,g]) - (r.h.s. of (<ref>))    ≤ϵ_1,  ∀ s ∈𝒮,    
       V_γ,ℳ([s,g]) - (r.h.s. of (<ref>))    ≥ϵ_2,  ∀ s ∈𝒮.

In fact, the above optimization solves (<ref>) for  V_γ,ℳ.
 Second, after evaluating the current coherent risk function, an improvement is carried out either by changing the parameters of existing I-states, or if no new parameters can improve any I-state, then a fixed number of I-states are added to escape the local minima (Steps 14-17). This is described in Section <ref>.





















































 §.§ Escaping Local Minima by Adding I-States


At some point of running the algorithm,  no I-state may be improved with further iterations, i.e., ∀ g∈ G, the corresponding convex optimization (<ref>) yields an optimal value of ϵ = 0. Then, policy iteration has reached a local minimum if and only if V⃗_γ,ℳ(g) is tangent to the backed up value function for all g∈ G <cit.>. The dual variables corresponding to the Improvement Constraints in  (<ref>) provide those belief states that are tangent to the  risk function. The process for adding I-states  involves forwarding the tangent beliefs one step and then checking if the value of those forwarded beliefs can be improved. The procedure for adding I-states is provided in Algorithm <ref>.




 
Algorithm <ref> can be understood as follows. Assume that
a tangent belief b exists for some I-state g. Instead of directly improving the value of the
tangent belief, the algorithm tries to improve the value of forwarded
beliefs reachable in one step from the tangent beliefs. First, the forwarded beliefs are computed (Step 4-8). Then, the corresponding  risk value functions are applied to a DP Backup (Steps 9-11). If some action α^*
and successor I-state g^* can in fact reduce the risk value (Step 12), then a new
I-state is added which deterministically leads to this action and
successor I-state (Steps 13-14). Note that at the end of the algorithm,
the newly added I-states, g_new have no incoming
edges, i.e., no pre-existing I-states transition to
g_new. However, when the other I-states are improved in subsequent
policy improvement steps, they generate transitions to any g_new
added. This new I-state then improves the value of the original tangent belief.














































§ NUMERICAL EXAMPLE



An  agent (e.g. a robot) has to autonomously navigate a two dimensional terrain map (e.g. Mars surface) represented by a 10× 10 grid world (100 states) with 15 obstacles of different shapes. At each time step the agent can move to any of its eight neighboring states (diagonal moves are allowed). Due to sensing and control noise, however, with probability δ a move to a random neighboring state occurs. The stage-wise cost of
each move until reaching the destination is 1, to account for fuel usage. In between the
starting point and the destination, there are a number of obstacles that the agent should
avoid. Hitting an obstacle incurs the cost of 10 leading to termination, while the goal grid region has reward 80. The discount factor is γ=0.95. After a move is chosen, the observation of  the agent is assumed to be binary, i.e., either an obstacle is detected in the next cell that the robot is moving to or not. Similar to <cit.>, in our simulations, we included an
obstacle and target position perturbation in a random direction to one of the neighboring grid
cells with probability 0.2 to represent uncertainty in the terrain map (recall the uncertainty in Mars terrain maps as shown in Figure 1).
 
The objective is to compute a safe (i.e., obstacle-free) path that is fuel efficient. To this end, we consider CVaR as the coherent risk measure. CVaR is given by 

    ρ_t(c_t+1) = inf_z ∈ℝ{ z + 1/α𝔼[  (c_t+1-z)_+|ℱ_t    ]                        },

where (·)_+=max{·, 0} and the infimum should be understood point-wise. In general, the confidence level α may be ℱ_t-measurable function with values in the interval (0,1). Here, we assume  α∈ (0,1). A value of α≃ 1 corresponds to a risk-neutral policy; whereas, a value of α≃ 0 is rather a risk-averse policy. For CVaR risk measure, (<ref>) can be computed as

    V_γ,ℳ([s,g]) =   ∑_α , g' , o ω(g',α| g,o) O(o|g') c([s,g],α) 
       + γinf_z ∈ℝ{ z + 1/α∑_g',s', o,α( V([s',g'])-z)_+
         × O(o| s)ω(g',α| g, o) T(s'| s,α)},

where the infimum on the right hand side of the above equation can either be solved by line search techniques or
by representation in terms of an elementary linear programming problem since it is convex in z <cit.> (the function (·)_+ is increasing and convex <cit.>).

 


Figure 2 depicts the policies and the value functions computed for the grid world based on the bounded policy iteration technique in Section <ref>. For these experiments, we used 2 internal states for the stochastic finite state controller and the corresponding convex optimizations were solved using CVX toolbox <cit.> in MATLAB.


 
 As it can be observed from Figure 2,    the risk-neutral policy
leads to shorter paths from different cells to the target. However,  on 100 perturbed scenarios, it performed poorly with 43 failures. On the other hand,
the risk-averse policy leads to longer routes from cells to the target chooses, but it resulted only in 3 failed scenarios. These results parallel those obtained in <cit.>, wherein  risk-averse policies in terms of CVaR for MDPs were studied.



§ CONCLUSIONS
 

We proposed a method based on bounded policy iteration and convex optimization to design risk-averse stochastic finite state controllers for POMDPs. Future research will explore risk-averse polices for POMDPs that maximize the  satisfaction probability of a set of high-level mission specifications in terms of temporal logic formulae <cit.>. Furthermore, the risk-averse policy synthesis technique will be applied for designing risk-averse planning policies for traversing on uncertain Mars surface (as depicted in Figure 1).




plain


