New Geometry Quantifies Non-Stationarity Cost in Adversarial MDPs

In dynamic decision-making problems, traditional analyses often equate the cost of non-stationarity with the magnitude of change in the loss function. However, a large change in loss might not alter the optimal policy, while a small change could necessitate a complete policy shift. This research proposes a more nuanced understanding. The paper develops a normal-fan geometry for finite-horizon adversarial Markov Decision Processes (MDPs) with fixed transitions. This framework views occupancy measures as a polytope, where each loss vector exposes an optimal face. Non-stationarity is then conceptualized as a path through this normal fan, where crossing a "wall" between cones signifies a change in the optimal policy and incurs regret. A key concept introduced is the "face-crossing price," which quantifies the minimum regret from maintaining a previous optimal policy under a new loss. This allows for an exact decomposition of dynamic regret into the intrinsic cost of policy shifts and within-face selection errors, effectively separating consequential non-stationarity from harmless variations.