Online Convex Optimization in Adversarial Markov Decision Processes

Aviv Rosenberg; Yishay Mansour

Source-linked AI summary

Online Convex Optimization in Adversarial Markov Decision Processes

Aviv Rosenberg, Yishay Mansour

arXiv:1905.07773v1May 19, 2019cs.LGcs.AIstat.ML

TL;DR

The paper addresses online learning in episodic adversarial MDPs with arbitrary losses and unknown transition dynamics. It combines online mirror descent with confidence-based transition estimation to support convex episode-level performance criteria. The resulting UC-O-REPS algorithm achieves near-optimal regret bounds and improves prior expected-loss bounds.

Problem
The paper studies adversarial episodic MDPs where losses change arbitrarily between episodes while the transition function is unknown, including criteria beyond expected average loss.
Method
UC-O-REPS combines Online Mirror Descent with UCRL-2 and selects occupancy measures within confidence sets for unknown transition dynamics.
Results
UC-O-REPS achieves near-optimal regret bounds for convex performance criteria and improves the known expected-average-loss bound, with guarantees holding with high probability.
Takeaways & Limitations
The adversarial MDP model can cover varied episode-level objectives, including risk-sensitive and robust objectives, while retaining strong regret guarantees.
Takeaways & Limitations
The loop-free layered-state assumption simplifies the analysis, and unknown-transition bandit feedback remains an open difficult problem.

Abstract

from arXiv · show

We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show $\tilde{O}(L|X|\sqrt{|A|T})$ regret bound, where $T$ is the number of episodes, $X$ is the state space, $A$ is the action space, and $L$ is the length of each episode. Our online algorithm is implemented using entropic regularization methodology, which allows to extend the original adversarial MDP model to handle convex performance criteria (different ways to aggregate the losses of a single episode) , as well as improve previous regret bounds.

1. Introduction

The paper studies adversarial MDPs with arbitrarily changing losses and unknown transitions, proposing UC-O-REPS to support convex performance criteria and improve regret bounds.

1. Introduction: Adversarial MDPs allow losses to change arbitrarily while retaining a fixed stochastic transition function, with regret measured against the best stationary policy in hindsight.This setting addresses nonstationary losses while preserving stationary dynamics.
1. Introduction: UC-O-REPS combines Online Mirror Descent with UCRL-2 to handle arbitrary losses and unknown transition dynamics in adversarial MDPs.OMD addresses online convex optimization, while UCRL-2 supplies techniques for unknown stochastic transitions.
1. Introduction: Convex performance criteria extend adversarial MDPs beyond expected average loss to objectives such as risk-sensitive and robust optimization.These criteria aggregate episode losses in different ways, including trade-offs involving multiple loss functions.
1. Introduction: The resulting regret bound is near-optimal in the general model and improves prior bounds for expected average loss, especially when the action space is large.The supplied passages state that the bounds hold with high probability and improve the known bound of Neu et al. (2012).
1. Introduction: Prior work considered settings with known transitions, bandit feedback, or unknown transitions, motivating the paper’s combined treatment of unknown dynamics and adversarial losses.The related work includes algorithms based on experts, bandit methods, and Follow the Perturbed Leader.

2. Problem Formulation

The problem is episodic online decision-making in a loop-free MDP with unknown transitions, arbitrary multidimensional losses, and a chosen convex criterion for aggregating each episode.

2. Problem Formulation: The state space is divided into L non-intersecting layers with transitions only between consecutive layers, simplifying the process into L-step episodes.The first and last layers are singletons, representing the initial and terminal states.
2. Problem Formulation: Loss functions may be multidimensional and are chosen arbitrarily across episodes, while the learner experiences them only after trajectory losses are aggregated by the criterion.This supports modeling multiple losses simultaneously without imposing statistical assumptions on their sequence.
2. Problem Formulation: In each episode, the learner follows a stationary stochastic policy from the initial state through consecutive layers until reaching the terminal state.The policy specifies an action distribution π(a|x) at each visited state.
2. Problem Formulation: The learner minimizes total loss under a performance criterion that aggregates the losses collected along each trajectory.The criterion can represent total expected loss, worst-case loss across multiple functions, or risk-sensitive loss.
2. Problem Formulation: Regret compares the learner’s criterion value with that of the best stationary stochastic policy.The comparator is optimized over stationary stochastic policies.
2. Problem Formulation: When transitions are unknown, observed trajectories are used to estimate the transition function and the learner’s performance criterion.With known dynamics, the trajectory would not be needed to compute the criterion.

3. Occupancy Measures

The paper reformulates convex performance criteria in adversarial MDPs using occupancy measures, turning policy selection into online convex optimization over a structured decision space.

3. Occupancy Measures: Occupancy measures represent state-action-transition visitation probabilities induced by a policy and transition function.For each state-action-transition tuple, qP,π records the probability of visiting that transition during an episode.
3. Occupancy Measures: The feasible set Δ(M) is characterized by flow constraints, and each feasible occupancy measure induces a transition function and policy.These structural properties exploit the loop-free MDP assumption and preserve the relationship between occupancy measures and the underlying MDP.
3. Occupancy Measures: Convexly-measurable criteria admit a convex criterion function f_C that evaluates expected aggregated losses from occupancy measures.The criterion function can also define performance criteria implicitly because the algorithm requires only f_C.
3. Occupancy Measures: Selecting occupancy measures instead of individual policies rewrites regret minimization as online convex optimization over Δ(M).This reformulation is the basis for applying online optimization methods to general convex performance criteria.
3. Occupancy Measures: The framework covers criteria formed by applying a convex function to aggregated transformed losses, including the stated class of examples.Convexity follows from composing a convex function with a linear function.

4. The Algorithm

UC-O-REPS combines confidence sets for unknown transitions with online mirror descent over occupancy measures, selecting optimistic updates under adversarially changing losses.

4. The Algorithm: UC-O-REPS combines UCRL-2-style confidence sets with OMD over occupancy measures to handle unknown transitions and arbitrary loss sequences.Confidence sets address transition uncertainty, while OMD chooses occupancy measures within those sets.
4.1. Confidence Sets: The confidence sets shrink over epochs while containing the true occupancy-measure set with high probability.Epochs end when visits to a state-action pair double, after which transition estimates and confidence sets are updated.
4.2. Online Mirror Descent: For each episode, OMD balances minimizing the current criterion loss against staying close to the previous occupancy measure using KL divergence.The update uses a sub-gradient of f_C and an unnormalized KL-divergence regularizer.
4.2. Online Mirror Descent: The unconstrained OMD update exponentially reweights the previous occupancy measure by the current criterion sub-gradient.The resulting projection problem is a convex optimization problem that can be solved efficiently with non-negativity constraints.
4.2. Online Mirror Descent: The algorithm’s optimization is convex because the KL objective and occupancy-measure constraints are convex, with strong duality ensured by Slater’s condition.Lagrange multipliers yield an optimal finite solution to the constrained problem.

5. Analysis

The analysis decomposes regret into online-convex-optimization and unknown-dynamics components, then bounds both for UC-O-REPS under convex performance criteria. The resulting theorem gives high-probability regret guarantees, with the classical total expected-loss case as a corollary.

Regret decomposition: The analysis splits regret into an approximation term from unknown transitions and a policy-selection term handled by online convex optimization.The two terms respectively capture transition-estimation error and the error from choosing suboptimal policies.
Classical criterion: The total expected-loss setting follows immediately as a corollary because its induced function is linear in the occupancy measure and 1-Lipschitz for losses bounded by 1.The corollary substitutes the total expected-loss criterion into the general theorem.
Unknown transitions: The unknown-dynamics component estimates transition probabilities, constructs confidence sets, and selects occupancy measures from those sets even when they are not exact occupancy measures of the true MDP.The resulting bounds control the distance and loss difference between policies evaluated in the true and optimistic MDPs.
Online optimization: The online component uses Online Mirror Descent, convexity, subgradients, and entropic regularization to control changing loss functions and convex episode criteria.The proof adapts standard OMD regret analysis to occupancy measures and subgradients of the induced performance function.

6. Conclusions and Future Work

The paper combines OMD with UCRL-2 to learn in adversarial MDPs with unknown transitions and changing losses. It extends the model to convex performance criteria and establishes near-optimal regret bounds, while leaving sharper transition-dependent and bandit-feedback guarantees open.

Contributions: The proposed algorithm combines OMD for online convex optimization with UCRL-2 for reinforcement learning under unknown transitions.The setting allows losses to change arbitrarily between episodes.
Results: A sharper regret bound proportional to L|X|sqrt(|A|T) is obtained for the general setting, with improved dependence on the action-space size over prior work.The supplied conclusion identifies the bound as near-optimal in the extended model.
Contributions: The model is extended from expected average loss to convex performance criteria, including risk-sensitive and robust objectives.These criteria aggregate episode losses in application-dependent ways.
Future work: Open questions include achieving an L|X|sqrt(|A|T) bound in the model and extending the method to bandit feedback with unknown transitions.The bandit challenge arises because inverse-probability loss estimators require transition probabilities that are unavailable.

A. Proof of Theorem 4.2 Cont.

The proof reformulates the learner’s update as a constrained convex optimization problem and solves it through Lagrange multipliers. The resulting expressions connect occupancy-measure updates to value, error, normalization, and dual variables.

Optimization formulation: The learner’s update is formulated as a convex optimization problem over nonnegative occupancy-measure variables and flow-related constraints.The formulation includes normalization and transition-consistency inequalities with auxiliary slack variables.
Dual derivation: Lagrange multipliers eliminate auxiliary slack terms and yield an equivalent Lagrangian for the occupancy-measure update.The derivation differentiates with respect to slack and occupancy variables before simplifying the dual representation.
Update structure: The occupancy update’s derivative contains a log-ratio to the previous iterate, a normalization multiplier, Bellman potentials, and the OMD subgradient term.This structure reflects entropic regularization together with flow constraints and the current convex-loss subgradient.
Dual solution: Solving the stationarity conditions identifies normalization constants and reduces the remaining computation to a dual problem over the associated value and multiplier variables.The proof substitutes the updated occupancy measure back into the Lagrangian to obtain the dual formulation.

B. Proof of Theorem 5.2

The proof bounds the transition-estimation contribution by comparing occupancy measures induced by confidence-set transition functions with those induced by the true dynamics. It combines induction, concentration, martingale arguments, and UCRL-2 counting bounds.

Occupancy comparison: The transition-estimation term is controlled through the L1 distance between occupancy measures generated by estimated and true transition functions.The proof introduces ξt(x,a) as the L1 transition discrepancy for each state-action pair.
Layerwise propagation: An induction over episode layers propagates one-step transition discrepancies into bounds on state-action occupancy differences.The argument establishes the claim at the first layer and extends it recursively to later layers.
High-probability control: Confidence-set validity and concentration control the transition discrepancies simultaneously across layers with high probability.A union bound yields probability at least 1−2δ for the relevant collection of bounds.
Cumulative bound: The cumulative discrepancy is bounded using UCRL-2-style epoch counts, Jensen’s inequality, and martingale-difference arguments.Summing over layers, episodes, and state-action pairs completes the transition-estimation bound.