Strategies for convex potential games and an application to decision-theoretic online learning

  • 2021-11-24 17:52:55
  • Yoav Freund
  • 0

Abstract

The backwards induction method due to Bellman~\cite{bellman1952theory} is apopular approach to solving problems in optimiztion, optimal control, and manyother areas of applied math. In this paper we analyze the backwords inductionapproach, under min/max conditions. We show that if the value function is hasstrictly positive derivatives of order 1-4 then the optimal strategy for theadversary is Brownian motion. Using that fact we analyze different potentialfunctions and show that the Normal-Hedge potential is optimal.

 

Quick Read (beta)

loading the full paper ...