Regret Bounds for Online Portfolio Selection with a Cardinality Constraint
Online portfolio selection is a sequential decision-making problem in which a learner repetitively selects a portfolio over a set of assets, aiming to maximize long-term return. In this paper, we study the problem with the cardinality constraint that the number of assets in a portfolio is restricted to be at most k, and consider two scenarios: (i) in the full-feedback setting, the learner can observe price relatives (rates of return to cost) for all assets, and (ii) in the bandit-feedback setting, the learner can observe price relatives only for invested assets. We propose efficient algorithms for these scenarios, which achieve sublinear regrets. We also provide regret (statistical) lower bounds for both scenarios which nearly match the upper bounds when k is a constant. In addition, we give a computational lower bound, which implies that no algorithm maintains both computational efficiency, as well as a small regret upper bound.
Summary  The paper studies the online portfolio selection problem under cardinality constraints and provides two algorithms that achieve sublinear regret. One algorithm handles the full information setting and the other algorithm handles the bandit feedback setting. Furthermore, the paper provides lower bounds for both the full information and bandit feedback settings. The approach that both algorithms take is to split the problem into two learning problems. One problem is to learn the optimal combination of assets and the other problem is to learn the optimal portfolio. To learn the optimal combination of assets a version of either the multiplicative weights algorithm (full information) or exp3 (bandit feedback) is used. To learn the optimal portfolio the Follow The Approximation Leader (FTAL) algorithm is used. Finally, the papers provides three experiments in which the two new algorithms and three baseline algorithms are evaluated on one synthetic data set and two real world data sets.   Strengths and weaknesses  The problem that is solved in this paper has nice practical applications. The analysis of the algorithm was elegant and surprisingly simple after splitting the problem into two parts. After the splitting in two parts the analysis almost directly follows from applying standard algorithms with their standard regret bounds. On the downside, since for each combination of assets a version of FTAL is run the proposed algorithm for the full information has exponential runtime in the dimension. However, the authors show that the runtime cannot be improved while preserving the regret bound.   Since the FTAL  is run locally in the sense that each combination of assets gets its own instance of FTAL it would be interesting to see if the dependency on the constants C1, C2, C3, C4, and C5 in the regret bound can also depend on the optimal combination of assets.   I do not understand the reason for choosing these particular baseline algorithms. It seems very restrictive to only consider x_{t,i} \in {0, 1}, as FTAL can consider x_{t,i} \in [0, 1]. Therefore, the conclusion that algorithms 1 and 2 outperform the baseline algorithms is not very surprising. It appears a more informative baseline algorithm would be to use MWU/exp3 with gradient descent or exponential weights with a continuous prior.   The presentation of the material was reasonably clear, although the section on computational complexity is quite dense.    Minor comments - Figures 1-3: the colors of MWU_disc and Algorithm 2 are difficult to discern, perhaps use black instead of purple. - the statement “our algorithms are superior to others” seems a bit strong.  - line 349: the low of large number -> the law of large numbers.   The authors response cleared up some of the confusion regarding the simulations.