We study adversarial online learning with expert recommendations in a totally ordered action space, where the experts' recommendations may change and be reordered arbitrarily. Our focus is two-point feedback: on each round the learner plays two current recommendations, observes both, and pays their average. We study two problems. In the separated monotone problem, the loss is the sum of a hidden nondecreasing component and a hidden nonincreasing component, and a query reveals the two components separately. In the BV problem, the losses are bounded and have bounded variation (BV) along the order, and a query reveals only the loss. In the separated monotone problem, two paid observations achieve \[ O\bigl(\log(|\cF|T)\sqrt{T\log|\cF|}\bigr) \] regret against the best of $|\cF|$ experts, within a logarithmic factor of the classical full-information bound. For the BV problem, we obtain $\wtO(\sqrt T+|\cF|)$ regret. We give an application in dynamic pricing with expert advice, showing that two-option menus matches the full information rate up to $\log$ factors. The main technical ingredient is a marginal-preserving endpoint flow estimator. Two observations reveal a loss increment along the order; random paths supply telescoping identities that turn this local information into unbiased loss estimates for all current recommendations. A reversible pair sampler preserves the learner's intended marginal at both played actions. The estimator's second-moment and stability bounds support online updates for both feedback models.
We study dynamic pricing where a seller repeatedly interacts with a strategic, non-myopic buyer who has a fixed private valuation and discounts future utility. Prior work focused exclusively on posted-price mechanisms, where the seller gives a take-it-or-leave-it offer. For our first result, under geometric discounting $γ_t = γ^{t-1}$, we show that menu mechanisms consisting of allocation-payment contracts achieve $O(T_γ)$ regret, where $T_γ$ is the buyer's effective discounted time horizon. We also establish a $Ω(T_γ)$ lower bound, demonstrating the bound is tight. Considering the geometric discounting buyer with a constant discount factor, our bound is $O(1)$, while prior bounds using posted-price mechanisms incur an unavoidable $Ω(\log\log T)$ factor in regret. Our second contribution is more conceptual in nature. The problem of dynamic pricing sits at the intersection of two paradigms: learning with strategic agents in computer science / machine learning and revelation-principle-based mechanism design in economics, yet their relationship has remained unclear. We establish an equivalence between these two classes of mechanisms in our single-buyer setting: any adaptive indirect menu mechanism can be converted into an incentive-compatible direct mechanism with no less revenue, and conversely, any such direct mechanism can be implemented by an adaptive indirect menu mechanism with no less revenue. Consequently, the two classes achieve identical optimal regret. The adaptive, data-driven algorithms of online learning and explicit type elicitation from direct revelation type mechanisms are two languages towards solving the same problem.