The Application of Online Learning Algorithms to Regret Minimization

Abstract

In this thesis, we investigated a sequential decision making problem. We tested different policies for online portfolio optimization: for a given number of assets and a time horizon, the weights on assets are rebalanced at every time step according to a certain policy and the final wealths the policies yield with the same returns are compared. The objective function is to minimize the cumulative regret with respect to the expert portfolio; that is, the constant rebalanced portfolio (CRP) with future knowledge. After having tested the ExponentialWeighted Average Approach (EWA), the Online Gradient Descent Strategy (OGD) and the Online Newton Step Algorithm (ONS), we concluded that OGD outperforms the other two strategies: EWA and ONS. We also implemented an algorithm that induces sparsity in portfolios and observed that a sparse portfolio with future knowledge has the minimum regret with respect to the expert CRP, and performs better than the online policies EWA, OGD, and ONS. Our results showed that Optimal CRP > Sparse CRP >> OGD > ONS > EWA >> MVP (minimum variance portfolio). Since the best performing online method is shown to be OGD, OGD is used as the policy to rebalance stock portfolios in the second part of this thesis. In the second part, we developed a program that takes as inputs the current wealth, current monthly expense, current monthly income, the time horizon the person would like to consider, and residency of the person. The program returns the optimal percentages of wealth that should be kept in stocks, long term and short term corporate bonds, and cash; and makes a suggestion as to whether or not the person should retire.