Risk-Sensitive Policies for Sustainable Renewable Resource Allocation

1 Introduction

In this paper, we consider a broad class of MDPs that can be used as a model for the management of a renewable resource. While the most common examples are probably living resources, such as animal populations or forests, other types of resources such as time, energy, and financial resources can be also considered [Ermon et al., 2010]. In fact, the problem of managing the stock of a resource dynamically changing over time is quite general and it arises in many different fields under different names. In particular, in a renewable resource allocation problem, the stock of a (valuable) resource is dynamically growing over time. Such growth processes might occur on a continuous or discrete time scale, they are subject to nonlinear dynamics and they are affected by randomness. When we also factor in social and economic aspects, these multiple levels of complexity can easily lead to very challenging sequential decision making problems.

Most of the work [Clark, 1990; Conrad, 1999] in the literature on the management of such resources is based on riskneutral formulations, where the goal is that of maximizing the sum of (discounted) economic rewards over time. However, in many domains arising in the emerging field of Computational Sustainability [Gomes, 2009], this approach can be inadequate. In fact in many such problems, high stakes decisions with potentially catastrophic outcomes (such as the collapse of an entire ecosystem) need to be taken by carefully balancing social, economic and ecologic goals. More in general, a fundamental challenge of sustainability science [Clark, 2007] is how to take decisions that balance the welfare of current and future generations and to devise policies that provide guarantees on the welfare of future generations. In this context, risk-neutral approaches are usually not capable of providing such guarantees. For instance, in the case of the management of an animal population, policies that are too aggressive may cause the collapse of an entire population.

As a partial answer to these questions, we propose the introduction of decision theoretic concepts into the optimization frameworks, by leveraging the significant advancements made by the AI community. In general, we can model and solve MDPs with general utility functions [Liu and Koenig, 2006], so that we can capture the behavior of almost every rational decision maker [Von Neumann et al., 2007] and cast resource allocation problems into a much richer framework. In particular, in the context of natural resources, it is critical to introduce risk-averse attitudes of the decision makers by choosing suitable utility functions, as opposed to standard risk-neutral approaches. By enforcing risk-aversion, we obtain policies that are more cautious and less prone to those catastrophic outcomes that might endanger the welfare of future generations.

With similar goals, Ermon et al. [Ermon et al., 2010] propose the use of a worst-case scenario analysis (which is analogous to a game against nature) in order to minimize the risk of collapse in resource allocation problems. However, while a risk-neutral approach might be too optimistic, the worst-case scenario is often too pessimistic. To overcome these problems, we propose the use of an exponential utility function of the form U(x) = exp(γx) that maps revenues to utilities. Our approach is significantly more general, because by choosing the right value of γ we are able to capture a broad range of risk-attitudes between the two extreme cases of riskneutral and worst-case approaches. In fact, when the population becomes dangerously small, the revenue will drop and the exponential scaling will significantly penalize the utility of such scenarios. While on one hand we lose the theoretical lower-bound guaranteed by the game against nature approach, on the other hand in any practical application there is always another level of uncertainty affecting the estimated support of the probability distributions involved (i.e. the set of available moves in the game against nature framework). Therefore, in reality, such theoretical lower-bounds are less reliable than one might expect because of the uncertainty in the model parameters. Moreover, exponential utility functions are particularly suitable for sequential decision making problems because they are the only class of utility functions (together with linear ones) that satisfy the so-called delta property, that allows for optimal policies that are not historydependent and hence are easy to describe and to implement in real-world problems.

Previously, risk-sensitive policies for harvesting biological populations were considered in [Horwood, 1996]. The author extended some known optimality results to the risk-sensitive case for some continuous-time models which were originally introduced in [Clark, 1990]. However, except in the linear dynamics and quadratic cost case, the obtained results were heuristic or characterizations of the local optimality of the policies (with necessary but not sufficient conditions based on Pontryagin's Maximum Principle). In contrast, our main result (Theorem 2) proves that a general class of discrete-time MDPs with exponential utility functions admits a closed form optimal solution (i.e. with a given structure that allows for a compact analytical representation) that can be easily implemented by policy makers. These results are especially interesting because there are only a few MDPs with known closed form solutions. The proof is based on a generalized notion of concavity known as K-concavity originally introduced to study inventory control problems [Scarf, 1960]. In order to prove Theorem 2, we first show some useful results on the composition of K-concave functions that generalize some fundamental properties on the composition of standard concave functions.

We demonstrate the practical applicability of the proposed framework by studying the Pacific Halibut fishery management problem. This domain of applications is particularly important because marine fishery resources are one of the most poorly managed and most endangered ones due to overexploitation [FAO, 2005]. Our results provide new evidence that a new policy based on periodic closures of the fishery should be employed, instead of the traditional policy that harvests a constant proportion of the stock every year.

2 Preliminaries

2.1 Risk-sensitive MDP formulation

We consider a class of Markov Decision Processes that arises as a general model for many renewable resources allocation problems. Examples of such real-world problems are the management of natural resources such as animal species or forests, as described in detail in [Clark, 1990; Conrad, 1999; Ermon et al., 2010]. However, our model is more general and our results apply to a broad class of so called generalized inventory control problems [Scarf, 1960] that are extended with the introduction of a stock-dependent internal growth function. This framework is quite general and finds applications in many different fields. In fact, the stock variable can represent resources such as time, energy, natural and financial resources, depending on the application domains. These include natural resources management, supply chain management, vaccine distribution and pollution control [Ermon et al., 2010].

We consider a discrete-time continuous-space problem where the state variable xn ∈ R represents the available stock of the resource at time step n. The stock xn is modeled as a Markov Chain with non-linear dynamics evolving according to the following difference equation

where hn is the control variable, representing the amount of resource that is extracted or harvested at time step n. The internal growth processes are modeled using a stock recruitment function f(x) that is, in general, density dependent, in order to capture phenomena such as competition for limited food and habitat in animal populations. We suppose that there is a finite maximum stock size denoted by m. Uncertainty is introduced into the model using the random variables wn, assumed to be discrete and independent. As an example, in a fishery model wn are used to model factors such as weather conditions, climate change or the temperature of the water, all uncontrollable factors that affect the growth rate of the stock.

To complete the description of the MDP, we introduce a standard economic model used by [Clark, 1990; Conrad, 1999; Ermon et al., 2010] and others. We suppose that a harvest of size h generates a revenue equal to hp, where p is a fixed constant selling price. We assume that there is a marginal harvesting cost g(x) per unit harvested when the stock size is x and that each time a harvest is undertaken there is a fixed set-up cost K, independently of the size of the harvest. The net revenue (selling profits minus costs) associated with a harvest h from an initial population x is then given by

where

The marginal harvesting cost g(x) is assumed to be a decreasing function of x, so that harvesting becomes cheaper when the stock is abundant. We define x0 to be the stock size such that g(x0) = p, that is the zero profit level. As a consequence for all x > x0 we have that the function R(x) defined in Equation (2) is non decreasing and convex.

2.2 Risk-sensitive optimization

According to Utility Theory [Von Neumann et al., 2007], every rational decision maker who accepts a small number of axioms has a utility function U that maps their real-valued wealth levels w into finite real-valued utilities U(w) so that they always choose the course of action that maximizes their expected utility.

In decision theory, the attitude towards risk of a decision maker is represented by the utility function U. Given a random variable v (often called a lottery), in general not all outcomes of v are equally significant: the decision maker ranks them according to the utility function U. In particular, a decision maker is risk-averse if E[U(v)] ≤ U(E[v]) meaning that he prefers the expected value of the lottery over the lottery itself.

While MDPs with general utility functions can be solved using the method proposed in [Liu and Koenig, 2006], the resulting optimal policy is defined in an extended state-space and is in general history-dependent. Of particular interest for the case of sequential decision making is the case of exponential (and linear) utility functions, that as shown in [Howard and Matheson, 1972] have a constant aversion to risk that provides the kind of separability required to implement dynamic programming and lead to optimal policies that are not history dependent. Instead of considering the traditional case of linear utility function (risk-neutral approach), in this paper we consider the case of exponential utility functions, so that the resulting policies can be easily described and implemented in practice.

Since we are interested in fully observable closed loop optimization approaches, where decisions are made in stages and the manager is allowed to gather information about the system between stages, we introduce the concept of policy. A policy is a sequence of rules used to select at each period a harvest level for each stock size that can possibly occur. In particular, an admissible policy π = {μ1, . . . , μN} is a sequence of functions, each one mapping stocks sizes x to harvests h, so that for all x and for all i

We consider the problem of finding an admissible policy π = {μi}i∈[1,N ] that minimizes

where the lottery is the total discounted net revenue

where xn is subject to (1) and hn = μn(xn), with initial condition x1 = x and

and 0 < α < 1 is the discount factor. The parameter γ is called risk sensitiveness, and the larger γ the more risk averse the decision maker is. Intuitively, this is because small realizations of J πN (x) are heavily penalized by the exponentiation. In the limit γ → ∞, the smallest realization of J πN (x) dominates the expectation in (4), as happens in the worst-case analysis situation [Ermon et al., 2010].

3 Properties of K-concave Functions

To study the optimal policies for this risk-sensitive MDP model, we will make use of a property known as K-concavity. The standard definition of K-concavity is the following:

Definition 1. A function β(·) is K-concave on an interval I if for all x, y, x < y, and for all b > 0 such that y + b ∈ I

Equivalently, β(·) is K-concave if for all x < z ∈ I and λ ∈ [0, 1]

The fundamental result on K-concavity is the following Lemma:

Lemma 1. The following properties hold:

1. A concave function is 0-concave and hence K-concave for all K ≥ 0 .
2. If β1(q) and β2(q) are K1-concave and K2-concave, respectively, for constants K1 ≥ 0 and K2 ≥ 0, then aβ1(q)+bβ2(q) is (aK1 +bK2)-concave for any scalars a > 0 and b > 0.
3. If β(·) is nondecreasing and concave on I and ψ is nondecreasing and K-concave on [infx∈I β(x), supx∈I β(x)] then the composition ψ ◦ β is K-concave on I
4. If β(·) is a continuous, K-concave function on the interval [0, m], then there exists scalars 0 ≤ S ≤ s ≤ m such that
5. β(S) ≥ β(q) for all q ∈ [0,m].
6. Either s = m and β(S) - K ≤ β(m) or s < m and β(S) -K = β(s) ≥ β(q) for all q ∈ [s,m).
7. β(·) is a decreasing function on [s,m].
8. For all x ≤ y ≤ s, β(x) - K ≤ β(y).

This is a dual version of the properties of K-convex functions proved for example in [Bertsekas, 1995, Section 4.2].

In order to prove our main results, we use the following novel theoretical results on the vector composition of Kconcave functions, that significantly generalize the standard results on the composition of regular concave functions.

Theorem 1. Let φ : Rn → R be a concave function non-decreasing in each of its arguments such that φ(K + x1, . . . ,K+xn) ≤ K+φ(x1, . . . , xn) for all x1, . . . , xn,K and let β1(x), . . . , βn(x) be a family of functions R → R such that βi(x) is K-concave and non-decreasing for i = 1, . . . , n. Then γ(x) = φ(β1(x), . . . , βn(x)) is K-concave.

Proof. We have

Lemma 2. The log-sum-exp function φ : Rn → R defined as φ(z1, . . . , zn) = - log ∑ e-zi is a concave function non-decreasing in each of its arguments such that φ(K + x1, . . . ,K + xn) ≤ K + φ(x1, . . . , xn) for all x1, . . . , xn,K ∈ R.

Proof. From [Boyd and Vandenberghe, 2004] we have that

is convex and non decreasing in each of its arguments, so

is a concave function non-decreasing in each of its arguments. Moreover

4 Main Results

4.1 Optimal policy

A policy π is called an optimal N-period policy if Eπ [exp(-γJ πN (x))] attains its infimum over all admissible policies at π for all x. We call

the optimal expected utility function, where Π represents the set of all admissible policies. As shown in [Marcus et al., 1997], by making use of the Delta property the problem can be decomposed and solved by Dynamic Programming using Bellman-like equations:

for all t > 0, with boundary condition Sγ 0 (x) = 1. Equation (6) can also be rewritten in terms of the escapement z = x-h as

Given the presence of fixed costs K, a harvest is undertaken if and only if there exists 0 ≤ z ≤ x such that

or equivalently if and only if

We introduce

so from (8) we get that a harvest is undertaken at time t if and only if there exists 0 ≤ z ≤ x such that

If we prove that P γ t (x) is continuous and strictly Kconcave, then using Lemma 1-d we can characterize the optimal policy at time step t. In fact by Lemma 1-d there exists two thresholds St ≤ st such that condition (10) is met if and only if x > st. If x > st, the optimal escapement z in Equation (7) is exactly the other threshold St by the properties proved in Lemma 1-d. This policy is known in the Operations Research community [Scarf, 1960] as a nonstationary S -s policy, because the levels St and st depend on the time index t.

Our main result is that we can prove that a nonstationary S - s policy is optimal for the risk-sensitive MDP model we considered. In particular, if the marginal cost function g satisfies

(meaning that g does not decrease too rapidly) where G is the integral of g and m is the maximum stock size, then the following theorem holds:

Theorem 2. For any setup cost K > 0, risk sensitiveness γ > 0 and length of the management horizon N, if wn are independently distributed, f(·, w) is nondecreasing and concave for any w, and g is non increasing and satisfies condition (11), then the functions P γ n (x) defined as in (9) are continuous and K-concave for all n = 1, . . . ,N. Therefore, there exists a non-stationary S - s policy that is optimal for the risk-sensitive optimization problem. The corresponding optimal expected log-utility functions -1/γ logSγn (x) are continuous, nondecreasing and K-concave for all n = 1, . . . , N.

Proof. From Equation (11) there exists k ∈ R such that

The proof is by induction on the length of the control horizon N. The base case N = 0 is trivial because Sγ 0 (x) = SγN (x) = 1 for all x, and therefore - log(SγN (x)) = 0 is continuous, nondecreasing and kγ-concave. Now we assume that - log Sγn-1 (x) is continuous, nondecreasing and kγ-concave, and we show that P γ n (x) is continuous and Kconcave, and that - logSγn (x) is continuous, nondecreasing and kγ-concave.

Using the composition result of Lemma 1, since f(·,w) is nondecreasing and concave for all w and by the inductive hypothesis, we have that - log Sγn-1 (f(x,w)) is kγ-concave. From the definition of expectation we obtain

so that using Theorem 1 and Lemma 2, we get that - log E[Sγn-1 (f(x, wn))] is kγ-concave as well.

By Equation (9) using Lemma 1-b, since -R(x) is concave and by induction - log E[Sγα t-1 (f(x,wt))] is kγα-concave, P γ n (x) is k-concave and therefore also K-concave. By Equation (9) we get that P γ n (x) is continuous, because by the inductive hypothesis Sγα n-1 (x) and R(x) are continuous.

Since P γ n (x) is K-concave, by Lemma 1-d there exists two thresholds Sn ≤ sn associated with P γ n (x) with the properties of Lemma 1-d. From the Dynamic Programming Equation (7) and what we have shown on condition (10), we have that

-

From Equation (13) we get Sγn (x) is continuous because Pn(x) and R(x) are continuous and by definition P γ n (sn) + R(sn) = P γ n (Sn)+R(sn)-K. To showlog Sγn (x) is nondecreasing, we consider several cases. First notice that since harvesting below the zero profit level x0 is not profitable and reduces the marginal growth of the stock, it must be the case that sn ≥ Sn ≥ x0. Given x2 > x1 > sn ≥ x0 we have:

-

because R is nondecreasing for x ≥ x0. In the case 0 ≤ x1 < x2 ≤ sn we obtain:

-

Then is must be the case that - log Sγn (x2) + log Sγn (x1) ≥ 0 because if - log Sγα n-1 (x) is nondecreasing , then Sγα n-1 (x) must be non-increasing, so for each ω, Sγα n-1 (f(x1, ω)) ≥ Sγα n-1 (f (x2, ω)).

In order to show that - log Sγn (x) is kγ-concave, by Equation (12) it is sufficient to show that - logSγn (x) is (K + τ )αγ-concave using definition (5). When sn < x < y, Equation (5) holds because R(·) is τ -concave. When x < y ≤ sn,

- logSγn (x) = γα(P γ n (x) + R(x)) and therefore using by Lemma 1-b Equation (5) holds because P γ n (x) is K-concave and R(·) is τ-concave. Finally, when x ≤ sn < y Equation (5) can be written as

Theorem 2 completely characterizes the structure of the optimal policy, but it does not provide an analytical solution for the values of Sn, sn. These values can be computed numerically by discretizing the continuous domains and solving the resulting MDP by Dynamic Programming. Our knowledge on the structure of the optimal policy guarantees the consistency of the method, that is a (uniform) convergence of the discretized solution to the true one as the discretization step goes to zero. Moreover, the a priori knowledge on the structure of the optimal policy reduces the computational complexity of the algorithm used to compute the numerical values of the S - s thresholds characterizing the policy. In fact the policy for a given time step t is completely characterized by the corresponding threshold st (that can be computed for example by bisection) and by the optimal escapement St associated with any state x > st.

5 The Pacific Halibut Marine Fishery

The North American Pacific halibut fishery is one of the most important fisheries of the western coast of North America.

It is jointly managed by the governments of U.S. and Canada through the International Pacific Halibut Commission (IPHC) to provide rational management and avoid overfishing. In order to do that, every year the IPHC decides the total allowable catch (TAC), represented in our model by the decision variable hn.

5.1 Management problem formulation

We consider the biological model presented in [Ermon et al., 2010] to study Area 3A of the Pacific Halibut fishery, one of the 10 major regulatory areas in which waters are divided. Their model is based on 33 years of data from 1975 to 2007, extracted from IPHC reports, and provides a very good fit with the historical stock sizes. We briefly summarize their model.

In the context of a fishery management, the state variable xn represents the total biomass and the growth of the resource is due to reproduction. To model these growth processes, we consider a stochastic version of the Beverton-Holt model:

where sn = xn - hn is the escapement of fishing in year n. According to Equation (15), the stock size at the beginning of the next breeding season is given by the sum of two terms: the fraction of the population that survives natural mortality and the new recruitment. To account for variable factors and uncertainty (such as weather conditions or the temperature of the water) that affect the growth rate, we introduce stochasticity into the system in the form of seasonal shocks wn that influence the new recruitment part. We will (a priori) assume that wn are independent identically distributed uniform random variable with a finite support Iw = [1 - 0.11, 1 + 0.06]. The values of the parameters of Equation (15) fitted to the

Halibut population in Area 3A are taken from [Ermon et al., 2010] and reported in Table 1.

For the resource economics aspects of the model, we assume that there are two categories of costs involved: fixed costs (such as vessel repairs costs, license and insurance fees) and variable costs (such as fuel and wages). While the first component is independent of the size of the harvest, the second one depends on the effort involved. The sum of all the fixed costs will be denoted with K, and these costs will be incurred every year in which a harvest is undertaken.

The model for variable costs will capture the fact that harvesting is cheaper when the stock size is abundant. In particular, we assume that a harvest of size h that brings the stock size from x to x - h results in variable costs given by

for some q and b. The function c/(qxb ) is precisely the marginal harvesting cost function g(x) introduced earlier. Furthermore, we assume that there is a fixed constant selling price p independent of the size of the harvest and we assume a fixed discount factor α = 1/(1 + 0.05). The values of the parameters are estimated in [Ermon et al., 2010] and are reported in Table 1.

5.2 Optimal risk-sensitive policy

We compute the optimal risk-sensitive policy by solving Bellman Equations (7) using a Dynamic Programming approach for a discretized problem. In order to solve the problem, we need to discretize both the state space and the control space. In the experiments presented in this section we used a discretization step Δ = 0.25 × 106 pounds. Moreover, we also discretize the support Iw of the random variables involved, thus obtaining a completely discrete MDP that we can solve.

We computed the optimal risk-sensitive policy (R-S) for the Pacific Halibut fishery in Area 3A for several values of γ and for a management length N = 33 years. As predicted by Theorem 2, the optimal policy is of S - s type. In particular, given a fixed risk-sensitiveness γ, an optimal policy is characterized by tuples Sn, sn for n = 1, . . . , 33; at year n, the optimal policy prescribes to harvest the stock down to Sn if and only if the current stock is larger than sn. This type of management policy involves periodic closures of the fishery, where for several consecutive years no action is taken so that the population can recover. In particular, after it has been harvested down to S, it is optimal to wait for the stock to become larger than s before opening the fishery again.

Periodic closures of the fishery are also prescribed by the worst-case scenario policy considered in [Ermon et al., 2010], but the thresholds to be used are different, and in the case of a risk-sensitive policy they are dependent on the risksensitiveness γ used. However, this approach is very different from the Constant Proportional Policy (CPP) that has been traditionally used to manage the Halibut fishery, that harvests a fixed fraction of the current stock level every year in order to maintain the population at at level perceived to be optimal (also known as a constant escapement policy [Clark, 1990])

As we show in Table 2, S - s policies are superior to historical harvests and CPP policy in terms of total discounted revenue (the experiment is initialized with an initial stock size x1 = X1975 = 90.989 million pounds), both assuming a worst-case realization of the randomness and assuming uniform samples from Iw. While the worst-case policy is indeed (by definition!) optimal for a worst-case realization, the risk sensitive approach is far more versatile. In fact by choosing a suitable value of γ, we can take a more balanced attitude toward risk, giving us a much broader spectrum of possible alternatives, that range from close to worst-case (large values of γ) to something close to risk-neutral optimization (small value of γ).

6 Conclusions and future work

In this paper, we consider a general class of MDPs used to model renewable resources allocation problems and we prove the optimality of S - s policies in a risk-sensitive optimization framework. Our proof is based on a generalization of concavity known as K-concavity. As part of our proof, we significantly generalize some fundamental results on the composition of traditional concave functions.

Our framework generalizes previous approaches such as the worst-case analysis, since it provides more balanced approaches toward risk. In particular, it allows a range of risk behaviors, from a worst-case approach (for large γ) to a riskneutral approach (for small γ), as well as a broad spectrum of intermediate cases.

We apply our results to the Pacific Halibut fishery management problem, and find new evidence that a cyclic policy involving periodic closures of the fishery should be employed instead of the traditional constant escapement policies.

We are currently working towards an extension of the Kconcavity concept to multidimensional spaces, in order to generalize our results on the optimality of S-s policies to multidimensional settings. This would allow us to capture interesting scenarios involving for example the interactions between multiple species. Another interesting research direction is to examine whether the (multidimensional) Kconcavity concept arises in other traditional continuous state space or hybrid MDPs (e.g. in robotic applications) from the AI literature [Sutton and Barto, 1998], or can be used to efficiently compute approximate threshold-based policies to less structured scenarios.

7 Acknowledgments

This research is funded by NSF Expeditions in Computing grant 0832782.