Advances in Online Learning and Auction Design

The field of online learning and auction design is rapidly evolving, with a focus on developing innovative algorithms and mechanisms that can handle complex real-world scenarios. Recent research has explored the use of decentralized policies, adaptive decision-making, and collusion-proof mechanisms to improve efficiency and regret guarantees in various settings, including online price competition, bandit learning, and multi-step-ahead prediction. Notably, the development of novel algorithms such as PML-GLUCB and LR-CSSP has led to significant improvements in regret bounds and adaptivity. Furthermore, the design of auctions that can detect and prevent collusion has become a crucial area of research, with mechanisms such as Hybrid VCG showing promising results. Overall, the field is moving towards more robust and efficient solutions that can handle uncertainty, limited information, and strategic behavior.

Noteworthy papers include: Online Price Competition under Generalized Linear Demands, which proposes a novel decentralized policy that achieves near-optimal regret bounds. Regret Guarantees for Linear Contextual Stochastic Shortest Path, which introduces an algorithm that achieves a regret bound of O(K^2/3 d^2/3 |S| |A|^1/3 B_star^2 T_star log(1/delta)). Collusion-proof Auction Design using Side Information, which designs a Hybrid VCG mechanism that combines VCG with a posted-price mechanism to prevent collusion.

Sources

Online Price Competition under Generalized Linear Demands

Cascading Bandits With Feedback

A Best-of-Both-Worlds Proof for Tsallis-INF without Fenchel Conjugates

Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Prediction

Collusion-proof Auction Design using Side Information

Regret Guarantees for Linear Contextual Stochastic Shortest Path

Bandit Learning in Housing Markets

Leave-One-Out Learning with Log-Loss

Prior-free Collusion-proof Dynamic Mechanisms

Built with on top of