Princeton University Library Catalog

The Application of Online Learning Algorithms to Regret Minimization

Avcisert, Gokce [Browse]
Senior thesis
Bubeck, Sebastien [Browse]
Princeton University. Department of Operations Research and Financial Engineering [Browse]
Class year:
75 pages
Restrictions note:
Walk-in Access. This thesis can only be viewed on computer terminals at the Mudd Manuscript Library.
Summary note:
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.