A Two-level Reinforcement Learning Algorithm for Ambiguous Mean-variance Portfolio Selection Problem

1 Introduction

The modern portfolio selection theory has started to play an important role in both academia and industry of finance, after the seminal work of [Markowitz, 1952] who proposed the renowned mean-variance (MV) portfolio selection framework. After almost half century of struggle, [Li and Ng, 2000] succeeded in extending the Markowitz's static model into a multi-period setting and derived an analytical optimal portfolio policy through a novel way that embeds the timeinconsistent dynamic MV portfolio selection problem into a series of time-consistent control problems that are able to be solved by dynamic programming (DP). Most of the existing results in portfolio selection, including the dynamic MV problem with no-shorting constraint [Cui et al., 2014] and mean-CVaR [Strub et al., 2019], are based on the assumption that the investors have a full knowledge about the statistics of returns, while in the pure MV case, the knowledge of means and covariances of returns of risky assets will be sufficient. However, this assumption is not often the case in the real investment practice. In fact, the market condition is always time-varying and even for a short stationary time period, its statistical nature could still be unclear to investors. Therefore, the portfolio policy with a learning feature becomes more demanding than the classical one relying only on the historical market information. Especially we can invoke nowadays, for this purpose, the type of reinforcement learning (RL) algorithms which have been rapidly developed on solving dynamic decision-making problems ([Sutton and Barto, 2018; Bertsekas, 2019]).

∗Contact Author

In this paper, we consider an ambiguous MV portfolio selection problem with a mixture distribution on the returns of risky assets, where the proportions of different component distributions are assumed to be unknown to the investor, but being constants (in any time instant). It is reasonable to adopt such a framework where all component distributions in the mixture model are known to the investor in advance while the proportions are not, as each component distribution could be linked with a certain market mode (such as bull, bear, or neutral), and investors could have knowledge on each specific market mode from their past experience. On the other hand, it is usually difficult to estimate the probability by which a certain mode will occur in the future. Such an assumption has been already adopted in the literature, see, for example, [Zhu et al., 2014] who focused on a robust mean-CVaR problem. Moreover, given the prior belief of the investor, updating the proportions through foreseeable future observations during the process of solving such an ambiguous problem is indispensable for deriving an optimal policy with an active-learning feature. Unfortunately, such a coupling makes the solution process intractable by traditional methods such as DP, due to the very nonlinear and nonseparable nature of learning techniques in, for example, the expectation maximization (EM) algorithm [McLachlan and Peel, 2004] about upgrading the components' weights. We instead develop in this paper a two-level framework in order to derive an investment policy with a learning feature through the combination of i) the time-decomposed approach DP in the lower level for solving in parallel a family of modified scenario subproblems where all the possible sequences of component distributions are enumerated and listed in different scenarios and ii) a scenario-decomposed method, progressive hedging algorithm of [Rockafellar and Wets, 1991], in the upper level in order to iteratively aggregate the scenario solutions from lower layer based on the ambiguous proportions. Learning is finally achieved in a manner of rolling horizon.

2 ProblemFormulation

Consider a financial market with N risky assets and one risk-free asset, and a finite investment horizon T. For t = 0, 1, . . . , T - 1, the total return of the riskless asset at time t, denoted by rt, is deterministic and known, while the total return of risky assets, denoted by et = (e1t , . . . , eNt )′ ∈ RN , is random and assumed to be independently and identically distributed with a finite mixture model of M components,

where Dm stands for the mth component distribution with given mean µm and covariance Σm, and all p∗m ∈ [0, 1] as the corresponding mixed proportions satisfying ∑m p∗m = 1 are assumed to be fixed but unknown to the investor, leading to an uncertain statistics of the random returns. In this ambiguous situation, an MV investor seeks to develop some investment strategy ut = (u1t , . . . , uNt )′ ∈ RN , where each unt represents the dollar amount invested in the risky asset n (hence (xt - 1′ut) goes to the risk-free asset for the wealth level xt and 1 ∈ RN is the all-one column vector), so that the following dynamic MV problem with ambiguity is optimized,

where ϵ is the threshold of the expected final wealth specified by the investor, Pt = (e1t -rt, . . . , eNt -rt)′ = et-rt1 ∈ RN is known as the random excess total return at time t, and the notations Vare,p and Ee,p are used to emphasize that the variance and expectation are conducted not only on the randomness from the returns but also on the ambiguity from the proportions of the underlying mixture distribution. Note that the former uncertainty is irreducible as it is inherent in the risky asset by nature, while the latter is due to the lack of knowledge of the investor thus being reducible through learning. Besides, I0 = {(Dm)m, x0, p0} represents the initial information set at time 0 which are given and contains knowledge of each component distribution, the initial wealth, and the prior belief of the investor, denoted by p0 = (p01, . . . , p0M)′ , on the ambiguous component proportions. For example, the investor may start with p0m = 1/M for all m = 1, . . . ,M. During the whole investment period, the wealth level and assets' prices will be observed. Given the pairs of newlyobserved asset's price Sn t+1 and the previous one Sn t for every risky asset n, the total return at time t + 1 can be computed through

For simplicity, the new information set will directly include the realized return instead of the observed asset price and thus it satisfies the dynamics It+1 = {It, et+1, xt+1, ut}. The posterior belief on the ambiguous proportions, denoted by pt+1, is then updated based on It+1 as in the nonlinear function g through EM algorithm that has been widely adopted to numerically estimate the unknown parameters (here for the unknown proportions) in the mixture model.

To solve (AMV (ϵ)), we first borrow the idea from [Li and Ng, 2000] to convert the problem into an equivalent form,

However, (5) is still intractable mainly due to the very nonlinear and nonseparable characteristics in the EM learning process. Thus, we bypass the difficulty by dropping this learning constraint (5) and replacing it with a rolling-horizon way for proportions updating. The two-level framework we are going to propose in the next section is designed to solve a series of truncated problems starting from time τ , τ = 0, 1, . . . , T -1, to the fixed terminal time T as given below,

3 A Two-level Portfolio Policy Scheme

The core feature of the two-level idea generally lies in separating the ambiguity on proportions from the randomness in returns, instead of coupling them together when dealing with the overall problem. Since the two-level policy scheme relies not only on the well-known DP for solving portfolio problems under each specific scenario but also on the progressive hedging algorithm (PHA) with which some readers may not be familiar, we will first provide some preliminaries on both topics and for more details we suggest referring to [Li and Ng, 2000] and [Rockafellar and Wets, 1991], respectively.

3.1 Classical Mean-variance Portfolio Policy

If there is no ambiguity on the proportions p∗m, (AMV (ϵ)) reduces to a classical problem with sufficient knowledge on the returns (i.e., the mean and covariance of the mixture distribution), and can be solved analytically by following [Li and Ng, 2000] directly. Obviously, each scenario subproblem of (AET 0 (ϵ)) under our ambiguous setting can be just counted as one special case of [Li and Ng, 2000]. More precisely, a scenario j in our paper represents a sequence of component distributions along the time horizon of length T . For instance, one extreme scenario could be that the first component distribution happens T times, of which the scenario probability is (p∗1 )T if we know its exact proportion in the underlying mixture distribution. On top of that, we actually do not know at time 0 which scenario will really occur in the future. However, once given a specific scenario j, we are fully aware of the values of Ej[et] and Ej[ete′t ] for all t as we assume, and the scenario subproblem we are facing is

where the notation Ej is used to emphasize that the expectation on each et is computed under the scenario j. We continue to follow the steps in [Li and Ng, 2000] to attach the equality constraint (6) of the final wealth into the objective function and generate the corresponding Lagrangian problem with a Lagrangian multiplier λj > 0,

Solving (Lj(ϵ, λj)) is a standard application of DP that can be found in [Li et al., 1998]. Furthermore, due to the convexity of the problem, maximizing the dual function hj(λj; ϵ) w.r.t. λj would give rise the optimal feedback policy to (AEj(ϵ)). We list the final results as follows,

where

Besides, Ej [Pt] = Ej [et]-rt1 and Ej [PtP′t ] = Ej [ete′t ]- rtEj [et]1′ - rt1Ej [e′t ] + r2 t 1 · 1′ .

However, the above results are in general not the feasible solutions to (AET 0 (ϵ)), as they already presume the realizations of component distributions hereafter as if "stealing" the future information. The PHA we are going to introduce next is a general method to fix this issue.

3.2 Brief Introduction on Progressive Hedging Algorithm

Let us consider an optimization problem expressed in a multiscenario form,

where S represents a finite-scenario set and fj is a specific objective function if the scenario j happens. A policy y is defined as a mapping from S to RNT , and y(j) = (y′0 (j), y′1 (j), . . . , y′T-1 (j))′ denotes the actions taken at each time under the scenario j. The overall objective is adjusted by the scenario probabilities sj's that are evaluated at the beginning. For the mixture distribution with M members, the scenario set in rolling horizon is time-varying but always contains a permutation of all components randomly allocated to returns of (T - τ) periods, therefore we have |Sτ | = M T-τ at each time τ, and the scenario probability is nothing but just the product of the estimated proportions of corresponding components due to the statistical independence of returns among different time periods. Figure 1 exhibits a permutation scenario tree at τ = 0 from an example of two-period problem with a three-component mixture distribution thus nine scenarios, where the numbers in each circle node represent the indices of the components that returns follow at related times. It is clear that, for example, the scenario j6's probability is sj6 = p02 · p03.

The key feature of a qualified policy of multistage decisionmaking problems, compared with those from static cases, is that apart from satisfying the admissible set A as usual, it must avoid leveraging on the anticipative message since the information flow comes by time, i.e., it should also satisfy the non-anticipative constraint N so that it can be implemented in reality. The approach used in PHA to force scenario-specific policies into an implementable one is to take conditional expectations based on the subtree starting from each node within each scenario bundle. To see this, let us revisit the problem in Figure 1. The scenario-based solution, denoted by y0 , satisfies y0 (j) = argmin (Pj) for every j ∈ S = {j1, . . . , j9}, where (Pj) := {miny fj(y) over y ∈ Aj} is the scenario subproblem (without foreseen restriction) and Aj constitutes A := {y | y(j) ∈ Aj ∀j ∈ S}. Then the implementable policy in this example, denoted by ˆy0 = ((ˆ y0 0 )′ , (ˆ y0 1 )′ )′ : S → R2N , is computed such that i) when t = 0, ˆ y0 0 (j) = ∑k∈S sky0 0 (k) for each j ∈ S and ii) when t = 1 there are three bundles (subtrees) and for the scenarios belonging to the first bundle j ∈ J1 = {j1, j2, j3}, we have ˆ y0 1 (j) = ∑k∈J1 [sk/(sj1 + sj2 + sj3 )]y0 1 (k), and similar procedures to obtain the values of ˆ y0 1 on the bundles J2 = {j4, j5, j6} and J3 = {j7, j8, j9}.

Based on the implementable policy ˆy0 aggregated from the scenario-specific solutions, PHA then starts to iteratively (ν = 0, 1, . . .) solve the augmented Lagrangian problems,

for every j ∈ S, where wν serves as the Lagrangian multiplier with initial value w0 (j) = 0 ∀j, | · |2 denotes the 2-norm, and η > 0 is the predetermined penalty parameter. The optimal solutions of all (P ν j ) form yν+1 , which will be aggregated again into an implementable policy ˆyν+1 used in (P ν+1 j ) for all j in the next iteration. The Lagrangian multiplier is then updated via wν+1 = wν + η(yν+1 - ˆyν+1 ). Eventually, ˆyν+1 will converge to the real optimum y∗ of the primal problem (P) if fj(y) is convex w.r.t. y for every j.

3.3 Two-level Reinforcement Learning Framework

Now it is ready to come up with our two-level (TL) portfolio policy algorithm. It is actually an online rolling-horizon scheme. Since the policy considered in this paper belongs to the type of pre-committed ones, we fix at each time τ the value of λ, the Lagrangian multiplier to deal with the equality constraint (3), at λ0 that will be decided by a special scenario j0 using only the prior knowledge of the investor. More specifically, let λ0 = λ∗j0 in (10), where δj0 and θj0 are calculated based on Ej0 [et] = ∑m p0mµm and Ej0 [ete′t ] = ∑m p0m(µmµ′m +Σm) for all t = 0, 1, . . . , T -1. Note that p0m is the prior belief of the investor on the mth component of the mixture distribution. The TL procedure is presented through multiple steps as follows:

Step 0: Importing Initial Information

We specify x0 and ϵ, configure λ0, and set τ = 0.

Step 1: Solving the Truncated Problem at Time τ

This is the key part of the TL idea in order to solve (AET τ (ϵ)). Step 1.1: lower level for scenario subproblems. We solve the problem (AEj(ϵ)) subject to t = τ, τ + 1, . . . , T - 1 by the classical techniques as summarized in the Subsection 3.1 for each scenario j. Let us denote the feedback solution by

Step 1.2: upper level for iterative aggregations. These are done in terms of policies' coefficients:

Step 1.2.0: initialization. Set ν = 0, the penalty parameter η, and the tolerance level tol. The initial implementable feedback policy at time t, ˆu0t , is just given by

where

andK0tj andV0 tj are coming from the lower level in (11), and sτj is the scenario probability calculated based on the belief pτ of the proportions at time τ , and Jt is a scenario bundle at time t of a (T - τ)-stage permutation scenario tree. In fact, there is no difference for the aggregated results on different bundles from the same time stage of the permutation scenario tree structure, since the remaining subtrees starting from any node at the same time stage are actually identical. Therefore, we do not need to specify a bundle-oriented subscript for the coefficients ˆK0t and ˆV0 t in (13) and (14), while only a time index t is enough for them. For simplicity, we could always select Jt as the first scenario bundle at each time stage t. The initial w0 tj is set to be 0 for all t and all j. In fact, wν tj can be deemed as an affine function w.r.t. xt given the parameters ϵ and λ0, that is, wν tj (xt; ϵ, λ0) = Wν tj xt + Xνtj (2ϵ + λ0) with W0 tj and X0tj being zero vectors for ν = 0.

Step 1.2.1: solve and aggregate. In the following we are going to deal with the scenario-based augmented Lagrangian problem formed at time τ for different scenarios (note that we have already attached the equality constraint Ej[xT |Iτ ] = ϵ into the objective by the Lagrangian multiplier λ0 and simplified the expression of the following),

It turns out that, given ˆuνt = -ˆKνt xt + ˆVν t (2ϵ + λ0) and wν tj = Wν tj xt + Xνtj (2ϵ + λ0), the optimal solution of (LAEν j (ϵ)) can be obtained analytically by DP 1 again, leading to the following result, denoted by uν+1 tj (xt; ϵ, λ0), which is treated as the scenario-specific policy from (AEν j (ϵ)),

and the two coefficients satisfy the backward recursions derived from adopting DP on solving (LAEν j (ϵ)),

where I is an identity matrix with size N, and aν(t+1)j and bν(t+1)j are two elements in our optimal cost-to-go function of (LAEν j (ϵ)) with the terminal conditions aνTj = bνTj = 1

1 We ignore the derivation details and only list some necessary recursive formulas here, as this is a standard application of DP.

for all j and all ν, and they satisfy the backward recursions

Based on uν+1 tj in (15), we then get the related implemented policy denoted by ˆuν+1 t with coefficients similar as in (12),

where ˆKν+1 t = ∑j∈Jt (sτj/ ∑˜j∈Jt sτ˜j )Kν+1 tj , and ˆVν+1 t = ∑j∈Jt (sτj/ ∑˜j∈Jt sτ˜j )Vν+1 tj . Finally, the Lagrangian multiplier wν+1 tj is updated through

where coefficients satisfyWν+1 tj =Wν tj +η( ˆKν+1 t -Kν+1 tj ) and Xν+1 tj =Xνtj + η(Vν+1 tj - ˆVν+1 t ).

Step 1.2.2: check the stopping criteria. Let us calculate the distance dis between two iterative results defined by coefficients dis := ∑T-1 t=τ [ | ˆKν+1 t - ˆKνt |2 + | ˆVν+1 t - ˆVν t |2 + 1/η2 (| ˆWν+1 t - ˆWν t |2+|ˆXν+1 t - ˆXνt |2) ]. If dis > tol, we go back to the Step 1.2.1 by replacing ν with ν + 1; otherwise, we stop and execute the resulted time-τ policy only, that is, the action outputted by our TL scheme at time τ based on the current wealth xτ is

Step 2: Learning and Rolling Horizon

If τ = T - 1, TL process is done; otherwise let us move forward to the time τ + 1. We update the information set Iτ+1. In other words, we observe the new assets prices and calculate the realized total return eτ+1 by (2). We then update the wealth level xτ+1 by (4) and proportions belief pτ+1 by Algorithm 1 based on Iτ+1 to achieve the learning process of the investor, and it is then utilized to calculate the new scenario probabilities s(τ+1)j's of a new permutation scenario tree with remaining time length (T - τ - 1). Armed with the learning results, we are now going to solve the truncated problem at time τ +1, that is, we go back to the Step 1 and replace τ there by τ +1 and take into account the new posterior belief pτ+1 on the proportions and proceed thereafter.

Algorithm 1 Expectation maximization algorithm on estimating mixing proportions pτ+1 at time τ + 1

Input: Historical total returns Rt till time τ + 1, component distributions Dm, m = 1, . . . ,M, and the tolerance level ξ Output: Posterior mixing proportions pτ+1

• 1: Let κ = 0 and assign an initial value (for example, former proportions pτ ) to qκ := (qκ 1 , . . . , qκM )′ .
• 2: Calculate for every t = 1, . . . , τ + 1 and every m,

• 3: Set qκ+1 m = 1 τ+1 ∑τ+1 t=1 γm(Rt|qκ ) for each m.
• 4: if |qκ+1 - qκ |2 < ξ then
• 5: Set pτ+1 = qκ+1 , and return pτ+1.
• 6: else
• 7: κ ← κ+1, and go back to line 2
• 8: end if

In the above we show our TL policy framework step by step on solving the ambiguous MV portfolio selection problem, where we could see a close interaction between the time-decomposed approach DP and the scenario-decomposed method PHA. Note that the convex nature of (Lj(ϵ, λj)) for each scenario j guarantees the convergence of the TL method.

4 Experimental Study

In this section, we illustrate how to calculate those key coefficients that appears in our TL policy through a concrete example, and compare with another non-learning (NL) policy on their gaps from the full-knowledge (FK) policy, in order to reveal the significance of learning in an ambiguous financial market. This experimental work is done in MATLAB by the Monte Carlo simulations of returns from a Gaussian mixture model (GMM) as the underlying mixture distribution.

Example 1 (Gaussian mixture model). Consider a market with three risky assets (N = 3) and one risk-free asset, and an investment plan of forty periods (T = 40). The total return of risky assets eτ , τ = 0, 1, . . . , T - 1, is assumed to i.i.d. follow a GMM ∑Mm=1 p∗mN (µm, Σm) with three components (M = 3), where each N(µm, Σm) represents a multivariate Gaussian distribution with distinct means µ1 = (1.162, 1.246, 1.228)′ , µ2 = (1,1,1)′ , and µ3 = (0.962, 0.846, 0.828)′ that could reflect different market modes (bull, neutral, and bear) but a same covariance for simplicity,

It is reasonable to do so, since people in practice find that the means of stock returns fluctuate significantly when the market mode changes whereas the variances do not. The true proportions are set to be p∗1 = 0.5, p∗2 = 0.2 and p∗3 = 0.3 but are unknown to the investor. The total risk-free rate is rτ = 1.04 for all τ. Suppose the investor's initial wealth is scaled to be x0 = 1 and the target expected final wealth is ϵ = 2.

We analyse the above example from the following aspects.

Prior belief formation and proportions learning. Since assets' returns can be directly collected from the market even without any real investment, a suitable action for the investor in an ambiguous environment would be waiting and observing for a while before really entering into it. We adopt a preinvesting learning period with length T /2 = 20 for the investor to form the prior belief p0 on the proportions before starting to do the investment at τ = 0. In our experiment, this is done by sampling T /2 returns (corresponding to the time from τ = -(T/2-1) to τ = 0) based on the real GMM and the prior belief is estimated by EM method (Algorithm 1) as well using these samples. This leads to p0 = (0.3808,0.0251,0.5941)′ . Another set of T samples are also generated for the rollinghorizon learning period in our TL framework after time 0. In fact at any time τ , the whole historical observations with size of τ+T/2 will be used to update the proportions. Figure 2 exhibits these learning outcomes, where each horizontal line represents the level of true proportion p∗m while the waved curves represent the value movements of each pτm w.r.t. time τ based on one series of returns' samples in our experiment. The vertical dotted line points out the best estimation at τ = 22. Note that the learning by EM in general will finally converge to their true values as long as T is larger enough.

Comparison among different policies. According to the market data given in Example 1 and the prior belief obtained above, we get λ0 = -0.0079. After assigning η and tol, we calculate KT L τ and VTL τ in (20) for τ = 0, 1, . . . , T - 1, the two core coefficients in our TL policy uTL τ . In order to evaluate the TL scheme, another two kinds of policies are also obtained: the FK policy as a benchmark and the NL policy. More precisely, KFK τ and VFK τ can be computed via Kτj∗ and Vτj∗ in (7) for a special scenario j ∗ , under which Ej ∗ [et] and Ej ∗[ete′t ] are determined by real p∗m's. By replacing j ∗ with j0 that depends only on p0, we get KNL τ andVNL τ of the NL policy. Note that the FK policy cannot really be implemented in the ambiguous market and the NL policy treats the prior proportions as the "true" ones (thus no learning behaviors occur ever since). We finally demonstrate the improvement on the policy derivation with learning. This is done by calculating 2-norm of differences of key coefficients among three types of policies above and the results are listed in Figure 3. We see that our TL framework benefits from learning in general as it produces in the ambiguous environment a better policy that is closer to the benchmark, while the NL case keeps accumulating errors as time goes by. On the other hand, however, the TL policy is also easily affected by the learning outcome, since its closest distance to the FK policy occurs at the same time when the proportions estimation is the best (when τ = 22 with p22 = (0.4627,0.2014,0.3360)′ ), but after that the performance becomes worse due to the fluctuation on learning. This phenomenon is also detected when we change the pre-learning time length or the investment time horizon.

5 Conclusion

In this paper, we deal with an ambiguous mean-variance portfolio selection problem where the returns of risky assets follow a mixture distribution, and each component distribution is completely given while their proportions are not. Although this problem can be formulated as usual, demanding on the successive learning of the unknown proportions in the solution process makes it intractable by the conventional methods. We propose a two-level (TL) scheme from reinforcement learning prospective to derive suboptimal policies but with learning feature from a type of amended problems. Our TL approach combines the exact dynamic programming adopted in the lower level to deal with the uncertainty from the random returns given a certain series of base distributions along the future times, and a scenario-decomposed method progressive hedging algorithm applied in the upper layer to handle the uncertainty from the ambiguous proportions, and learning is achieved in a rolling-horizon way. Although several experiments have demonstrated the effectiveness of our TL algorithm, it could still be improved in the future by incorporating more active learning aspects, in the sense that all possible future learning results could be considered in advance when solving the approximated primal problem at time 0.