Background and motivation. We consider a principal interacting sequentially with a flow of self-interested agents that each consume information, take actions, and generate new information over time. The principal's goal is to maximize the aggregate utility of all agents, which necessitates agents to occasionally acquire new information by exploratory actions that might otherwise be deemed inferior from an empirical standpoint. Such exploratory actions help discerning the best actions over time, but they are also the core of misaligned incentives between the principal and the agents. While a desirable alignment of incentives may be achieved via monetary payments to the agents, such payments are often infeasible, impractical, or unethical. The essence of the Incentivized Exploration (IE) problem is to leverage information asymmetry to incentivize agents to take exploratory actions. Online learning algorithms are a natural vehicle for studying this problem.

An agent facing sequential decisions that are characterized by partial feedback needs to strike a balance between maximizing immediate payoffs based on available information, and acquiring new information that may be essential for maximizing future payoffs. This trade-off is captured by the multi-armed bandit (MAB) framework that has been studied and applied when at each time epoch payoff observations are collected on the actions that are selected at that epoch. In this paper we introduce a new, generalized MAB formulation in which additional information on each arm may appear arbitrarily throughout the decision horizon, and study the impact of such information flows on the achievable performance and the design of efficient decision-making policies. By obtaining matching lower and upper bounds, we characterize the (regret) complexity of this family of MAB problems as a function of the information flows. We introduce an adaptive exploration policy that, without any prior knowledge of the information arrival process, attains the best performance (in terms of regret rate) that is achievable when the information arrival process is a priori known. Our policy uses dynamically customized virtual time indexes to endogenously control the exploration rate based on the realized information arrival process.

In online advertising markets, advertisers often purchase ad placements through bidding in repeated auctions based on realized viewer information. We study how budget-constrained advertisers may bid in the presence of competition, when there is uncertainty about future bidding opportunities as well as competitors' heterogenous preferences and budgets. We formulate this problem as a sequential game of incomplete information, where bidders know neither their own valuation distribution, nor the budgets and valuation distributions of their competitors. We introduce a family of dynamic bidding strategies we refer to as "adaptive pacing" strategies, in which advertisers adjust their bids throughout the campaign according to the sample path of observed expenditures. We analyze the performance of this class of strategies under different assumptions on competitors' behavior. Under arbitrary competitors' bids, we establish through matching lower and upper bounds the asymptotic optimality of this class of strategies as the number of auctions grows large. When adopted by all the bidders, the dynamics converge to a tractable and meaningful steady state. Moreover, we show that these strategies constitute an approximate Nash equilibrium in dynamic strategies: The benefit of unilaterally deviating to other strategies, including ones with access to complete information, becomes negligible as the number of auctions and competitors grows large. This establishes a connection between regret minimization and market stability, by which advertisers can essentially follow equilibrium bidding strategies that also ensure the best performance that can be guaranteed off-equilibrium.