Yaxiong Liu

Yaxiong Liu, Atsuyoshi Nakamura, Kohei Hatano et al.

In this paper, we consider the low rank structure of the reward sequence of the pure exploration problems. Firstly, we propose the separated setting in pure exploration problem, where the exploration strategy cannot receive the feedback of its explorations. Due to this separation, it requires that the exploration strategy to sample the arms obliviously. By involving the kernel information of the reward vectors, we provide efficient algorithms for both time-varying and fixed cases with regret bound $O(d\sqrt{(\ln N)/n})$. Then, we show the lower bound to the pure exploration in multi-armed bandits with low rank sequence. There is an $O(\sqrt{\ln N})$ gap between our upper bound and the lower bound.

Yaxiong Liu, Ken-ichiro Moridomi, Kohei Hatano et al.

We consider a variant of online semi-definite programming problem (OSDP): The decision space consists of semi-definite matrices with bounded $Γ$-trace norm, which is a generalization of trace norm defined by a positive definite matrix $Γ.$ To solve this problem, we utilise the follow-the-regularized-leader algorithm with a $Γ$-dependent log-determinant regularizer. Then we apply our generalised setting and our proposed algorithm to online matrix completion(OMC) and online similarity prediction with side information. In particular, we reduce the online matrix completion problem to the generalised OSDP problem, and the side information is represented as the $Γ$ matrix. Hence, due to our regret bound for the generalised OSDP, we obtain an optimal mistake bound for the OMC by removing the logarithmic factor.