論文

© 2019 Neural information processing systems foundation. All rights reserved. Bandit combinatorial optimization is a bandit framework in which a player chooses an action within a given finite set A ? {0, 1}d and incurs a loss that is the inner product of the chosen action and an unobservable loss vector in Rd in each round. In this paper, we aim to reveal the property, which makes the bandit combinatorial optimization hard. Recently, Cohen et al. [8] obtained a lower bound ?(pdk3T/log T) of the regret, where k is the maximum `1-norm of action vectors, and T is the number of rounds. This lower bound was achieved by considering a continuous strongly-correlated distribution of losses. Our main contribution is that we managed to improve this bound by ?(vdk3T) through applying a factor of vlog T, which can be done by means of strongly-correlated losses with binary values. The bound derives better regret bounds for three specific examples of the bandit combinatorial optimization: the multitask bandit, the bandit ranking and the multiple-play bandit. In particular, the bound obtained for the bandit ranking in the present study addresses an open problem raised in [8]. In addition, we demonstrate that the problem becomes easier without considering correlations among entries of loss vectors. In fact, if each entry of loss vectors is an independent random variable, then, one can achieve a regret of Õ(vdk2T), which is vk times smaller than the lower bound shown above. The observed results indicated that correlation among losses is the reason for observing a large regret.

This paper studies spectral approximation for a positive semidefinite matrix in the online setting. It is known in [Cohen et al. APPROX 2016] that we can construct a spectral approximation of a given $n \times d$ matrix in the online setting if an additive error is allowed. In this paper, we propose an online algorithm that avoids an additive error with the same time and space complexities as the algorithm of Cohen et al., and provides a better upper bound on the approximation size when a given matrix has small rank. In addition, we consider the online random order setting where a row of a given matrix arrives uniformly at random. In this setting, we propose time and space efficient algorithms to find a spectral approximation. Moreover, we reveal that a lower bound on the approximation size in the online random order setting is $\Omega (d \epsilon^{-2} \log n)$, which is larger than the one in the offline setting by an $\mathrm{O}\left( \log n \right)$ factor.

In this paper, we study a matching market model on a bipartite network where agents on each side arrive and depart stochastically by a Poisson process. For such a dynamic model, we design a mechanism that decides not only which agents to match, but also when to match them, to minimize the expected number of unmatched agents. The main contribution of this paper is to achieve theoretical bounds on the performance of local mechanisms with different timing properties. We show that an algorithm that waits to thicken the market, called the $\textit{Patient}$ algorithm, is exponentially better than the $\textit{Greedy}$ algorithm, i.e., an algorithm that matches agents greedily. This means that waiting has substantial benefits on maximizing a matching over a bipartite network. We remark that the Patient algorithm requires the planner to identify agents who are about to leave the market, and, under the requirement, the Patient algorithm is shown to be an optimal algorithm. We also show that, without the requirement, the Greedy algorithm is almost optimal. In addition, we consider the $\textit{1-sided algorithms}$ where only an agent on one side can attempt to match. This models a practical matching market such as a freight exchange market and a labor market where only agents on one side can make a decision. For this setting, we prove that the Greedy and Patient algorithms admit the same performance, that is, waiting to thicken the market is not valuable. This conclusion is in contrast to the case where agents on both sides can make a decision and the non-bipartite case by [Akbarpour et al.,$~\textit{Journal of Political Economy}$, 2020].