Timezone: »

 
Poster
Regret Bounds for Online Portfolio Selection with a Cardinality Constraint
Shinji Ito · Daisuke Hatano · Hanna Sumita · Akihiro Yabe · Takuro Fukunaga · Naonori Kakimura · Ken-Ichi Kawarabayashi

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #142
in Thu Poster Session B »

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 that 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.

Keywords: Information Theory · Bandit Algorithms · Learning Theory · Online Learning · Convex Optimization · Decision and Control · Computational Complexity
[ Paper] 

Author Information

Shinji Ito (NEC Corporation, University of Tokyo)
Daisuke Hatano (RIKEN AIP)
Hanna Sumita ( Tokyo Metropolitan University)
Akihiro Yabe
Takuro Fukunaga (RIKEN AIP, JST PRESTO)
Naonori Kakimura (Keio University)
Ken-Ichi Kawarabayashi (National Institute of Informatics)

More from the Same Authors