Portfolio Choices with Orthogonal Bandit Learning

1 Introduction

Portfolio choice problems have had a profound influence on the finance industry ranging from pension fund to mutual fund management and from insurance to corporate risk management [Brandt, 2010]. Modern portfolio theory and analysis build upon the seminal work of Markowitz [Markowitz, 1952]. However, motivated by its noticeably poor performance in out-of-sample settings [Broadie, 1993], researchers have expended unremitting efforts of investigating novel approaches to attack portfolio choice problems, such as numerous variants of the Markowitz framework [DeMiguel et al., 2009a], the optimal growth portfolio based on the Kelly criterion [Thorp, 1971], and the linear programming based portfolio optimization [Konno and Yamazaki, 1991].

Meanwhile, the globalization and the rapid growth of market integration yield massive amounts of data in the finance industry, which promotes the study of advanced data analysis tools. In particular, as leading-edge analytical techniques, machine learning algorithms emphasize on on-line building, updating and applying models based on its efficient automated processing of large datasets. Accordingly, machine learning researchers have paid significant efforts to design real time data stream based trading strategies [Helmbold et al., 1998; Blum and Kalai, 1999; Borodin et al., 2004; Agarwal et al., 2006; Gy¨orfi et al., 2006; Li and Hoi, 2012]. Among them, the Kelly criterion purporting to achieve optimal return growth shows a popular choice. For example, one representative work captures and utilizes the moving average reversion phenomena of the stock market to maximize the return growth on investment [Li and Hoi, 2012]. A comprehensive survey about on-line portfolio strategies can be referred to [Li and Hoi, 2014], and the extensive references therein.

As a potent tool for designing on-line sequential decision strategies, the multi-armed bandit problem has been studied since the early 1950's [Robbins, 1952]. The pivotal idea of bandit learning is to acquire new information while optimizing rewards based on existing knowledge, which is known as the tradeoff between exploitation and exploration in reinforcement learning. Such a tradeoff naturally establishes a connection to the sequential decision process in portfolio choice problems. The illuminating paper by [Hoffman et al., 2011] adopts a multi-armed bandit strategy to design the portfolio of acquisition functions in Bayesian optimization. However, standard multi-armed bandits assume the rewards of each arm are drawn from i.i.d. (independent and identically distributed) random variables, whereas in practice financial asset returns are generally correlated. Moreover, standard bandit learning attempts to choose the best arm for action, while in portfolio choice problems investors tend to select multiple assets for investment. Although combinatorial multi-armed bandit algorithms have been proposed to select multiple arms, it makes binary decisions of selecting arms and equally distributes investments among them [Chen et al., 2013]. In contrast, the crux of portfolio choice problems lies in determining the optimal distributing weights among assets.

To grapple with those challenges in applying conventional bandit algorithms to portfolio choice problems, in this paper, we provide an orthogonal bandit learning algorithm to effectively make portfolio choices. In particular, we take advantage of the principal component decomposition to orthogonalize correlated assets, choose the Sharpe ratio as the riskadjusted reward function in the upper confidence bound bandit framework to make investment decisions, and combine the generated passive and active portfolio weights to construct a low-risk portfolio. Further, to validate the proposed strategy, we evaluate the performance from both risk-adjusted return and cumulative wealth. Our extensive empirical studies and comparisons over several market datasets lucidly illustrate the superiority of the proposed strategy. We believe this work is a step in the development of leveraging on-line machine learning algorithms for portfolio choice problems.

The remainder of the paper is organized as follows. Section 2 briefly reviews the background of bandit learning. In Section 3 we propose our portfolio strategy based on orthogonal bandit learning. Section 4 covers our experiments and comparative studies, including the discussion of the datasets, the evaluation metrics and the performance demonstration. Finally, Section 5 concludes.

2 Background

In this section, we first review the problem setting and the solution of the standard multi-armed bandit. Then we discuss major difficulties of applying the standard bandit learning to portfolio choice problems.

Given n arms that represent n actions or assets and time steps tk, k = 1, . . . ,m, at time tk each arm receives a bounded real-valued reward ri(tk), i = 1, . . . , n. In practice, each arm may receive a fixed reward of the value 1 with certain probability, or otherwise a reward of 0, which is called the Bernoulli multi-armed bandit. Further, the objective of bandit learning is to choose a series of arms, one for each time, to maximize the total rewards or minimize the regret. For stochastic bandits, denote by νi the expectation of the reward from the i-th arm. The largest reward is ν ∗ = maxi=1,...,n νi and the maximum reward after m plays is mν ∗ . Thus, the pseudo regret after m plays is defined by

where ik is the index of selected arm at time tk and rik (tk) is the corresponding reward [Lai and Robbins, 1985]. Besides this standard bandit setting, various variants have been studied, such as non-stochastic bandits [Auer et al., 2002], bandits in an adversarial environment [Auer et al., 1995], and bandits in a contextual setting [Langford and Zhang, 2008]. Analyses of the reward and regret over numerous types of bandits can be found in the survey by [Bubeck and Cesa-Bianchi, 2012].

Further, to solve the multi-armed bandit problem, one straightforward policy is called the ϵ-greedy approach. At each time tk, the player chooses the arm with the highest reward with a probability 1 - ϵtk , or randomly chooses an arm with a probability of ϵtk , where the two parts are corresponding to "exploitation" and "exploration", respectively. If we set ϵtk = 12/(d2k) with 0 < d < ∆∗ , the accumulated regret until the m-th step of the ϵ-greedy strategy is bounded by O(∆∗n ln(m)/k), where △∗ is the gap between the best expected reward and the expected reward [Auer et al., 2002]. On the other hand, different from the randomized policy as the ϵ-greedy approach, the upper confidence bounds (UCB) strategy has emerged as another popular choice for multi-armed bandit problems [Lai and Robbins, 1985]. After playing each arm once, at each time tk the best arm i∗ (tk) is selected according to the following objective:

where ¯ ri(tk) is the mean reward of the i-th arm and ki is the number of times that the i-th arm has been played so far. The second part of the above selection rule relates to the one-sided confidence interval for the average reward. It has been shown that the total regret at time tm of the UCB policy is bounded by the following quantity [Auer et al., 2002]:

Further, Thompson Sampling and its variants have been another popular approach [Scott, 2010; Graepel et al., 2010]. A recent empirical study shows that Thompson sampling outperforms other peer methods in several real-world benchmarks [Chapelle and Li, 2011]. The empirical success sparks the great use of bandit learning algorithms in a wide range of applications, such as clinic trials [Press, 2009], web analytics [Graepel et al., 2010], algorithm selections [Gagliolo and Schmidhuber, 2011], and news recommendations [Li et al., 2010]. In addition, the role of risk in bandit and on-line learning has started to be acknowledged and studied [EvenDar et al., 2006; Sani et al., 2012; Maillard, 2013].

Given those successful examples, however, how to apply bandit learning to portfolio choice problems is less investigated. The intrinsic distinctions of financial assets and investment conventions call for a novel approach of altering and morphing the standard bandits. First, the standard multiarmed bandits assume i.i.d. rewards for each arm, which in principle does not hold for financial asset returns. Second, the standard multi-armed bandits tend to select the best arm, while the portfolio choices often aim to select a set of assets for investment. Third, the standard multi-armed bandits rest on the reward mean as the objective function, whereas in finance investors focus on the risk-adjusted return. Fourth, the standard multi-armed bandits assume no available historical data, whereas public traded financial assets generally have sufficient amounts of data. As such, we present a new bandit learning algorithm in the UCB framework to address those challenges in on-line portfolio choices.

3 Methodology

In this section, we first introduce the notations and financial terms in this paper. Then we will derive the proposed orthogonal bandit algorithm to make portfolio choices.

3.1 Notation

We consider a frictionless, self-financing, discrete-time and finite horizon investment environment. The trading periods consist of tk = k∆t, k = 0, . . . ,m. In particular, ∆t could represent one week or one month in our study. We use k for short as the time step index to indicate the trading period at time tk hereafter. We assume that investors have access to n risky assets with the gross return from time tk-1 to tk as Rk = (Rk,1, . . . ,Rk,i, . . . ,Rk,n)⊤. The gross return Rk,i for the i-th asset is computed by Rk,i = Sk,i/Sk-1,i, where Sk,i and Sk-1,i represent the prices of the i-th asset at time steps tk and tk-1, respectively. In time, investors decide how to invest in those assets. The investment decision over a set of assets at time tk is determined by a column vector representing portfolio weights ωk = (ωk,1, . . . , ωk,i, . . . , ωk,n)⊤, where the portfolio weight ωk,i specifies the invested percentage of wealth in the i-th asset. The sum of all the portfolio weights always equals one, i.e.,

where 1 denotes a column vector with ones as its entities. In addition, ωk,i > 0 indicates that investors take a long position of the i-th asset, and ωk,i < 0 represents that investors take a short sale position of the i-th asset. In particular, a short sale position means that investors first borrow an asset for sale and then invest its liquidation in other assets. The negative sign of the short sale weight reveals that investors will confront with a loss if the price of this asset starts to mount.

3.2 Bandit with Orthogonal Portfolio

We denote by Σk the positive definite covariance matrix of the n asset returns Rk at time tk. The principal component decomposition of the covariance matrix Σk derives:

where the diagonal matrix Λk contains the eigenvalues of Σk in decreasing order, i.e., λk,1 > λk,2 > . . . λk,n > 0 and the columns of the orthogonal matrix Hk = (Hk,1, . . . ,Hk,i, . . . ,Hk,n) are the corresponding eigenvectors of Σk. In particular, the principal eigenvectors define a set of n uncorrelated portfolios with the return H⊤k Rk; the eigenvalues that are all nonnegative represent the variances of those uncorrelated portfolios; the orthonormal property of the matrix Hk implies:H⊤ k,iHk,j = δi,j (6)

where δi,j is the Kronecker delta function.

Further, to convert the principal eigenvectors into the portfolio weights satisfying the condition (4), we normalize each eigenvector by its sum and define ˜Hk = ( ˜Hk,1, . . . , ˜Hk,i, . . . , ˜Hk,n) as the normalized matrix with each column computed by 1 :

Therefore, the new set of n uncorrelated portfolios has the return ˜H⊤k Rk and the covariance matrix of the returns:

where the diagonal matrix ˜Λk with the i-th diagonal entity as ˜λk,i = λk,i/(H⊤ k,i1)2 characterizes the variances. For ease of

1 The denominator generally is non-zero, or it leads to a potential arbitrage chance by investing in the dollar-neutral portfolio Hk,i.

Algorithm 1 Orthogonal Bandit Portfolio

Inputs: m, n, l, ∆t, Rk, τ

for k = 1 → m do

Estimate the average return E[Rk] and covariance matrix of asset returns Σk by {R-τ+k, . . . ,Rk-1};

Implement the principal component decomposition as equation (5): Σk = HkΛkH⊤k ;

Compute the renormalized similarity matrices and eigenvalues (8): ˜Σk = ˜HkΣk ˜H⊤k = ˜Λk;

Compute the Sharpe ratio of each arm (10);

Compute the adjusted reward function of each arm (11); Select the optimal arms according to (11) from the first l and the next n - l orthogonal portfolios, respectively; Compute the optimal mixture weight θ∗ k by (12);

Compute the optimal portfolio weight ωk by (13);

Output:

The portfolio weight vectors ωk and the portfolio returns µk for k = 1, . . . ,m.

presentation, we call the new set of portfolios the orthogonal portfolios. The orthogonal portfolios represent the risk factors in the market. Market fluctuations can be characterized as moves along the eigenvector directions [Meucci, 2009]. At time tk the return and the variance of the i-th orthogonal portfolio are estimated as ˜Hk,iRk,i and ˜λk,i, respectively.

In addition, numerous empirical studies in finance show the covariance matrix of asset returns consists of a few significant factors and other relatively unimportant factors [Bai and Ng, 2002; Meucci, 2009]. In other words, the covariance matrix can be decomposed as the sum of n rank-one matrices:

where the first l factors are viewed as the systematic movement in market, industry and sector that investors should follow, and the next n - l factors are considered as the idiosyncratic risks that investors may explore to generate extra return. Current research shows no consensus on the cutoff number l across different markets or asset classes. Three to five significant factors are commonly observed in empirical research and for specific market main factors are relatively stable along with time period [Fama and French, 1993]. In our empirical study, the cutoff l chosen for different markets according to the critical point where we observe a dramatic drop in the descending eigenvalues agrees with the above observation. Thus, we choose one portfolio from the first l orthogonal portfolios as a passive investment and another from the next n - l orthogonal portfolios as an active investment. The former attempts to follow the market trend and enjoy the passive return; the latter represents the endeavor of adding potential extra returns from small factors [Grinold and Kahn, 2000].

Furthermore, to determine how to invest in those two subsets, we apply the UCB algorithm to the multi-armed bandit setting with l arms and n - l arms, respectively [Auer et al., 2002]. While standard multi-armed bandit algorithms hinge on the expected return of each arm as the proxy of reward, we capture the tradeoff between risk and return by adopting the Sharpe ratio as our proxy of reward ¯ ri(tk) [Sharpe, 1966]. Unlike the general utility function that needs some subjective parameters quantifying the risk-averse degree [Sani et al., 2012], the Sharpe ratio takes into account the return per risk unit directly. Specifically, at time tk the Sharpe ratio of the i-th arm, i.e., the i-th orthogonal portfolio, is computed by:

Next, by incorporating the one-sided confidence bound into the reward function, we determine the optimal arm for each subset by the objective function:

where ki stands for the number of times the i-th orthogonal portfolio has been chosen so far and τ represents the size of training data. As the historical information of assets is available, we incorporate it into the one-sided confidence bound through the length τ [Shivaswamy and Joachims, 2012].

Furthermore, after obtaining the optimal arms from the two subsets, we take the weighted average of them such that the total variance of the selected portfolio, i.e., λk,p, is minimized. Specifically, assume the i-th and j-th arms are selected from the two subsets, respectively. ˜Hk,i∗k and ˜Hk,j ∗ k are the corresponding uncorrelated portfolios. Thus, the portfolio mixture weight θ∗ k is computed by minimizing the total variance λk,p = θ2 k ˜λk,j ∗ k + (1 - θk)2˜λk,i∗k :

Therefore, we attain the portfolio mixed by the passive and active investment as:

Accordingly, the realized portfolio net return µk from time tk-1 to tk will be µk = ω⊤k Rk-1. In the above formulation, we estimate the covariance matrix Σk by a factor model [Fan et al., 2008] and estimate the average return E[Rk] by the James-Stein shrinkage estimator [Meucci, 2009]. They both rest on the historical data in sliding windows with the size of τ training data. Algorithm 1 succinctly summarizes the steps of constructing the proposed orthogonal bandit portfolio.

4 Experiments

In this section, we describe the experimental settings and report the out-of-sample performance. We conduct the experiments on several empirical datasets and compare with representative portfolio choice methods in both finance and machine learning communities.

4.1 Data

In our experiments, we follow [Shen et al., 2014] to choose two types of datasets for performance validation and comparison. The first benchmarks are the Fama and French (FF) datasets [Fama and French, 1992]. With the raw data from the US stock market, the FF benchmarks construct the portfolios for different financial segments. Specifically, the FF48 dataset contains monthly returns of 48 portfolios representing different industrial sectors, and the FF100 dataset includes monthly returns of 100 portfolios on the basis of size and book-to-market ratio. By virtue of the extensive coverage to asset classes and lengthy periods, the FF datasets are recognized as standard evaluation protocols and oft-adopted testbeds in the finance community. The second type benchmarks contain two datasets of actively traded assets, i.e., ETF139 and EQ181, which are crawled from Yahoo! Finance on a weekly base from 2008 to 2012. The ETF139 dataset consists of typical accessible asset classes for investors, i.e., exchange-traded funds, which have the advantages over conventional mutual funds of low costs, tax efficiency, and stocklike features. The EQ181 dataset represents the selection of the individual equities sampled from the large-cap segment of the Russell 200 index, covering 63% of total market capitalization. To avoid selection bias, we remove those stocks with missing historical data during our testing periods, thereby having a total of 181 stocks in the EQ181 dataset.

As summarized in Table 1, these two types of datasets embody different perspectives for performance assessment. The FF datasets essentially underscore the long-term performance of the proposed strategy. The period range contains highly volatile times in the stock market, such as "Black Monday" in 1987, the Internet bubble burst and September 11 terrorist attacks in 2001. Such long historical datasets would introduce limited selection bias and performance manipulation. On the other hand, the ETF and equity datasets underline the robustness of the proposed portfolio with respect to the higher trading frequency and the special market environment after the recent financial crisis that began in 2007 with the default of subprime mortgage loans.

4.2 Experimental Settings

Following the "rolling-horizon" settings in [Shen et al., 2014], we use sliding windows with the size of τ = 120 months/weeks of training data to construct portfolios for the subsequent month/week. For our comparative study, we consider the following competing methods: a) equally-weighted portfolio (EW); b) value-weighted portfolio (VW); c) conventional minimum-variance portfolio (MVP); d) on-line moving average reversion (MAR) based portfolio; e) naive bandit portfolio (NBP); f) the proposed orthogonal bandit portfolio (OBP). The first three portfolio strategies are typical baselines circulated in the finance community. For example, the EW portfolio is a naive approach yet has been empirically shown to mostly outperform 14 models across seven empirical datasets [DeMiguel et al., 2009b]. The VW portfolio mimics a market portfolio by weighing individual market components according to their market capitalization. The MVP portfolio has shown significant performance improvement over the Markowitz mean-variance portfolio [Jagannathan and Ma, 2003]. On the other hand, the MAR portfolio represents a more data-driven approach developed by machine learning researchers and outperforms 12 different portfolio strategies across five datasets [Li and Hoi, 2012]. The NBP portfolio implements the UCB bandit algorithm under the standard assumption of i.i.d. rewards without considering the correlations between assets. Specifically, it selects one asset at a time for investment.

4.3 Performance Metrics

We compare the out-of-sample performance of the portfolios by the standard criteria in finance [Brandt, 2010]: (i) Sharpe ratios; and (ii) cumulative wealth. The Sharpe ratio (SR) measures the reward-to-risk ratio of a portfolio strategy, which is computed as the portfolio return normalized by its standard deviation:

where the mean of portfolio net returns ˆµ and the corresponding standard deviation ˆσ are computed as

Since SR is a summary statistic of returns, we supplement this commonly used measure of investment performance with the time series plot of cumulative wealth (CW). While CW measures the total profit yield from the portfolio strategy across investment periods without considering any risks and costs, investors are commonly concerned about the growth of their investment. Starting the investment period with one dollar, CW is computed by

To further quantify the statistical significance of the difference in SR between two comparing portfolios, we also report the p-values under the corresponding SR results. To compute the p-values for the case of non-i.i.d. returns, we adopt the studentized circular block bootstrapping methodology in [Ledoit and Wolf, 2008]. In particular, we set the EW portfolio as the benchmark with 1000 bootstrap resamples, 95% significance level, and a block with the size of 5.

4.4 Results

Table 2 reports the SR values with the p-values over the entire investment period, where the best performance is highlighted in bold. Apparently, the proposed orthogonal bandit portfolio has achieved the highest risk-adjusted returns, i.e., Sharpe ratios, in all the four datasets. Since NBP has only achieved comparable performance with OBP in the FF48 dataset, it reveals that asset correlations play a crucial role in portfolio choice problems. In particular, in the ETF139 and the EQ181 datasets, the proposed OBP method has generated the highest SR with significant margins. In addition, we can gain confirmation from the p-values that the OBP method is statistically distinguishable from the simple yet powerful EW strategy in FF100 and ETF139. NBP works relatively better in ETF139 and EQ181. This observation likely indicates that the on-line bandit strategy is more efficacious for short-term investment.

Table 3 summarizes the terminal cumulative wealth of different portfolios in all the datasets. Echoing with its superior performance in risk-adjusted return, OBP has generated the greatest increase in wealth among all the competing approaches. For the long investment periods such as the FF48

and FF100 datasets, the OBP method has produced significantly more wealth than the market itself, increasing the final wealth by 28.5% and 215.7%, respectively.

Figure 1 shows the time series curves of the cumulative wealth over the investment periods. OBP has demonstrated the highest wealth level in most of time. In particular, the illustration of its wealth cumulative trends that are generally disparate from others implicitly implies the distinction of its design principles. Our approach may perform even better if investors inject domain knowledge into the OBP framework that we illustrate here.

5 Conclusion

In this paper, we tackle the portfolio choice problems by an orthogonal bandit algorithm. Our novel algorithm has addressed the conundrum of making portfolio choices via multi-armed bandits with orthogonal portfolios. In particular, we orthogonalize generally correlated financial assets to create orthogonal portfolios through the principal component decomposition for the standard bandit learning framework; we incorporate the Sharpe ratio from the finance field as a risk-adjusted reward function into the UCB algorithm to direct investment; we further synergistically combine the generated passive and active investments to construct a lowrisk portfolio suitable to normal investors. Our future work not only includes appropriately generalizing and enriching the current framework to encompass more practical concerns in portfolio choice problems, such as position constraints, transaction costs and taxes [Shen and Wang, 2015; Dammon and Spatt, 2012], but also contains studying theoretical underpinning of the bandit problems they may bring.