Online Markov decision processes with policy iteration (情報論的学習理論と機械学習 情報論的学習理論ワークショップ(IBIS2015))

Yao Ma, Hao Zhang, Masashi SugiyamaIEICE 2015

Abstract

This paper introduces OMDP-PI, a practical and computationally efficient algorithm designed for Online Markov Decision Processes (MDPs) where reward functions are non-stationary and change over time. By integrating a closed-form update rule with linear function approximation, the authors provide a method that achieves sublinear regret. This approach effectively bridges the gap between theoretical online learning and practical reinforcement learning, making it applicable to large or continuous state spaces where traditional linear programming methods fail to scale.

Introduction

In classical Markov Decision Processes, an agent seeks to maximize rewards within an environment defined by fixed transitions and reward functions. However, real-world scenarios—such as robotic task adaptation or shifting market conditions—are rarely static. These scenarios are better modeled as Online MDPs, where the reward function is revealed only after the agent acts and can change at every discrete time step.

The primary challenge in Online MDPs is the minimization of regret: the difference between the total reward an agent actually accumulates and the reward it could have achieved using the single best fixed policy in hindsight. Previous algorithmic solutions often required intensive computation, such as solving complex linear programs at every step, or lacked the ability to scale to large state spaces. OMDP-PI addresses these limitations by utilizing a policy iteration framework that is both theoretically sound and computationally tractable.

The OMDP-PI Algorithm

The Online MDP with Policy Iteration (OMDP-PI) algorithm follows a structured recursive loop at each time step $t$:

  1. Policy Improvement: The agent updates its current policy ($\pi_t$) based on the cumulative average of all previously observed reward functions and the preceding value function estimate.
  2. Action and Revelation: The agent executes an action according to the updated policy. Subsequently, the environment reveals the current reward function ($r_t$).
  3. Value Update: The agent updates its estimate of the value function ($V_t$) using a recursive rule: $V_t = (1 - \gamma_t)V_{t-1} + \gamma_t V_{r_t}^{\pi_t}$.

Key Technical Innovations

  • Closed-Form Updates: For environments with manageable state spaces, the value function update can be solved directly via matrix inversion. This provides a significant speed advantage over iterative solvers.
  • Gibbs Policy: The algorithm employs a Gibbs (softmax) policy, which facilitates a smooth balance between exploring new strategies and exploiting known high-reward paths.
  • Linear Function Approximation: To overcome the "curse of dimensionality" in continuous or high-dimensional spaces, the authors extend OMDP-PI to use linear function approximation ($V(s) \approx \theta^\top \phi(s)$). This allows the agent to generalize learning across similar states rather than treating every state as a unique entity.

Experimental Evaluation

The algorithm was rigorously tested in a simulated Grid World environment. The setup consisted of a $16 \times 16$ grid (256 states) where an agent's goal was to navigate toward a destination. To simulate real-world complexity, actions were stochastic (30% chance of unintended movement), and states were clustered into $4 \times 4$ "super-grids" sharing reward characteristics.

To test the "online" adaptability, the reward functions were shifted every 5,000 episodes. The results demonstrated that the agent successfully identified optimal trajectories even as the reward landscape changed. Crucially, the average regret vanished as the number of episodes increased, confirming the algorithm's ability to converge toward optimal behavior in non-stationary environments.

Theoretical Significance and Insights

The authors mathematically prove that OMDP-PI achieves a sublinear regret bound of $O(T^{C_v})$, where $C_v < 1$. This theoretical guarantee ensures that as time progresses, the agent's average performance converges to that of the best possible fixed strategy.

A notable feature of the algorithm is its "lazy" update mechanism. By basing policy improvements on the average of past rewards rather than just the most recent one, the agent avoids overreacting to transient environmental fluctuations. This leads to more stable learning curves and robust performance against adversarial reward changes.

Limitations and Future Directions

While OMDP-PI represents a significant step forward, it operates under two primary assumptions:

  1. Known Transitions: The agent is assumed to have prior knowledge of the transition probability matrix $P$. Future work could involve learning transitions and rewards simultaneously.
  2. Full-Information Feedback: The model assumes the agent can observe the entire reward function after each step. Adapting the algorithm for bandit feedback—where only the reward for the specific action taken is visible—remains a critical area for further research.

In conclusion, OMDP-PI provides a robust framework for applying policy iteration to the online setting, offering a scalable solution for complex, dynamic control problems.

Summary updated

BibTeX
@inproceedings{ma2015online,
  author = {Yao Ma and Hao Zhang and Masashi Sugiyama},
  title = {{Online Markov decision processes with policy iteration (情報論的学習理論と機械学習 情報論的学習理論ワークショップ(IBIS2015))}},
  booktitle = {IEICE},
  year = {2015},
}

Loading related content...

Figure