Many problems in computer vision and recommender systems involve low-rank
matrices. In this work, we study the problem of finding the maximum entry of a
stochastic low-rank matrix from sequential observations. At each step, a
learning agent chooses pairs of row and column arms, and receives the noisy
product of their latent values as a reward. The main challenge is that the
latent values are unobserved. We identify a class of non-negative matrices
whose maximum entry can be found statistically efficiently and propose an
algorithm for finding them, which we call LowRankElim. We derive a
$\DeclareMathOperator{\poly}{poly} O((K + L) \poly(d) \Delta^{-1} \log n)$
upper bound on its $n$-step regret, where $K$ is the number of rows, $L$ is the
number of columns, $d$ is the rank of the matrix, and $\Delta$ is the minimum
gap. The bound depends on other problem-specific constants that clearly do not
depend $K L$. To the best of our knowledge, this is the first such result in
the literature.

本文提出了一种名为 LowRankElim 的算法，该算法能够在一定时间复杂度下对一个非负矩阵寻找其的最大值，并且在文献中该类结果首次出现。

随机低秩赌博机

Stochastic Low-Rank Bandits

We consider influence maximization (IM) in social networks, which is the
problem of maximizing the number of users that become aware of a product by
selecting a set of "seed" users to expose the product to. While prior work
assumes a known model of information diffusion, we propose a novel
parametrization that not only makes our framework agnostic to the underlying
diffusion model, but also statistically efficient to learn from data. We give a
corresponding monotone, submodular surrogate function, and show that it is a
good approximation to the original IM objective. We also consider the case of a
new marketer looking to exploit an existing social network, while
simultaneously learning the factors governing information propagation. For
this, we propose a pairwise-influence semi-bandit feedback model and develop a
LinUCB-based bandit algorithm. Our model-independent analysis shows that our
regret bound has a better (as compared to previous work) dependence on the size
of the network. Experimental evaluation suggests that our framework is robust
to the underlying diffusion model and can efficiently learn a near-optimal
solution.

该论文考虑了社交网络中的影响最大化问题，提出了一种可快速从数据中学习的新颖参数化框架并开发了 LinUCB 算法来解决问题。