We consider the problem of incentivizing exploration with heterogeneous agents. In this problem, $N$ bandit arms provide vector-valued outcomes equal to an unknown arm-specific attribute vector, perturbed by independent noise.Agents arrive sequentially and choose arms to pull based on their own private and heterogeneous linear utility functions over attributes and the estimates of the arms’ attribute vectors derived from observations of other agents’ past pulls. Agents are myopic and selfish and thus would choose the arm with maximum estimated utility. A principal, knowing only the distribution from which agents’ preferences are drawn, but not the specific draws, can offer arm-specific incentive payments to encourage agents to explore underplayed arms. The principal seeks to minimize the total expected cumulative regret incurred by agents relative to their best arms, while also making a small expected cumulative payment. We propose an algorithm that incentivizes arms played infrequently in the past whose probability of being played in the next round would be small without incentives. Under the assumption that each arm is preferred by at least a fraction $p > 0$ of agents, we show that this algorithm achieves expected cumulative regret of $O (N \e^{2/p} + N \log^3(T))$, using expected cumulative payments of $O(N^2 \e^{2/p})$. If $p$ is known or the distribution over agent preferences is discrete, the exponential term $\e^{2/p}$ can be replaced with suitable polynomials in $N$ and $1/p$. For discrete preferences, the regret’s dependence on $T$ can be eliminated entirely, giving constant (depending only polynomially on $N$ and $1/p$) expected regret and payments. This constant regret stands in contrast to the $\Theta(\log(T))$ dependence of regret in standard multi-armed bandit problems. It arises because even unobserved heterogeneity in agent preferences causes exploitation of arms to also explore arms fully; succinctly, heterogeneity provides free exploration.

We consider online content recommendation with implicit feedback through pairwise comparisons, formalized as the so-called dueling bandit problem. We study the dueling bandit problem in the Condorcet winner setting, and consider two notions of regret: the more well-studied strong regret, which is 0 only when both arms pulled are the Condorcet winner; and the less well-studied weak regret, which is 0 if either arm pulled is the Condorcet winner. We propose a new algorithm for this problem, Winner Stays (WS), with variations for each kind of regret: WS for weak regret (WS-W) has expected cumulative weak regret that is $O(N^2)$, and $O(N\log(N))$ if arms have a total order; WS for strong regret (WS-S) has expected cumulative strong regret of $O(N^2 + N \log(T))$, and $O(N\log(N)+N\log(T))$ if arms have a total order. WS-W is the first dueling bandit algorithm with weak regret that is constant in time. WS is simple to compute, even for problems with many arms, and we demonstrate through numerical experiments on simulated and real data that WS has significantly smaller regret than existing algorithms in both the weak- and strong-regret settings.

We present a Bayesian sequential decision-making formulation of the information filtering problem, in which an algorithm presents items (news articles, scientific papers, tweets) arriving in a stream, and learns relevance from user feedback on presented items. We model user preferences using a Bayesian linear model, similar in spirit to a Bayesian linear bandit. We compute a computational upper bound on the value of the optimal policy, which allows computing an optimality gap for implementable policies. We then use this analysis as motivation in introducing a pair of new Decompose-Then-Decide (DTD) heuristic policies, DTD-Dynamic-Programming(DTD-DP) and DTD-Upper-Confidence-Bound (DTD-UCB). We compare DTD-DP and DTD-UCB against several benchmarks on real and simulated data, demonstrating significant improvement, and show that the achieved performance is close to the upper bound.

Independent spanning trees (ISTs) on networks have applications in networks such as reliable communication protocols, the multi-node broadcasting, one-to-all broadcasting, reliable broadcasting and secure message distribution. However, there is a problem on ISTs on graphs: If a graph G is n-connected (n ≥ 1), then there are n ISTs rooted at an arbitrary vertex on G. This problem has remained open for n ≥ 5. In this paper, we consider the construction of ISTs on Möbius cubes—a class of hypercube variants. An O(N log N) recursive algorithm is proposed to construct n ISTs rooted at an arbitrary vertex on the n-dimensional Möbius cube Mn, where N = 2n is the number of vertices in Mn. Furthermore, we prove that each IST obtained by our algorithm is isomorphic to an n-level binomial-like tree with the height n + 1 for n ≥ 2.