Introduction
Traditional planning frameworks, such as Markov Decision Processes (MDPs), rely heavily on the Markov property: the assumption that the future state depends only on the current state. However, many real-world phenomena—such as wind speeds in energy grids or price fluctuations in financial markets—exhibit significant temporal dependencies or "memory." While one could theoretically expand the state space to include historical features to satisfy the Markov property, this often leads to the "curse of dimensionality," rendering the problem computationally intractable.
This paper introduces the Scenario-POMDP, a framework that bypasses the need for complex transition modeling by utilizing a library of weighted historical "scenarios." By treating the underlying scenario as a partially observable variable, agents can leverage historical patterns to make more informed decisions in non-Markovian environments.
Methodology
The Scenario-POMDP model represents the environment using a set of scenarios $X$, where each scenario is a sequence of actual historical states. The state space is factored into a triplet $(m, x, t)$:
- $m$: The domain-level state (e.g., current task status or battery levels).
- $x$: The hidden scenario currently being followed.
- $t$: The current time index within that scenario.
Scenario Weighting and Planning
As the agent interacts with the environment, it receives observations $o_t$. It updates its belief by assigning weights to scenarios in the library based on their similarity to the observed sequence. A common metric used is the sum of squared errors between the observation and the corresponding segment of the historical scenario.
To handle the potentially massive number of scenarios, the authors employ Partially Observable Monte-Carlo Planning (POMCP). This allows the agent to sample from the weighted scenario distribution to simulate potential futures, effectively performing pattern matching to select the optimal action $a$ without exhaustive computation.
Key Insights: Scenarios vs. Markov Models
A critical observation of this work is the failure of standard Markovian models to capture the realistic variance of time-series data. As shown in Figure 2, a second-order Markov chain's mean prediction tends to flatten quickly, losing the characteristic "shape" and volatility of real-world events like wind gusts. In contrast, the scenario-based approach preserves these long-term dependencies, providing a much richer basis for planning.
Experimental Evaluation
The framework was evaluated on two real-world datasets:
- Sotavento Wind Farm: Over 40,000 scenarios of 24-hour wind speed data from Galicia, Spain.
- Financial Markets: Historical daily closing prices for two major companies spanning 15 years.
Results in Smart Grid Management
In task-scheduling experiments designed to match energy demand with volatile wind supply, the Scenario-POMDP (implemented as POMCP 1) demonstrated superior performance. As illustrated in Figure 6, the proposed method significantly reduced the cost increase relative to an "omniscient" planner compared to standard MDP and consensus-based baselines.
The POMCP 1 variant achieved costs only ~5% higher than the theoretical optimum, while the MDP planner and consensus algorithms lagged behind with 15% and 33% higher costs, respectively. Similar success was observed in stock option trading, where the scenario-based agent outperformed both random and MDP-based strategies by effectively capturing non-linear market trends.
Conclusion and Future Work
The Scenario-POMDP offers a robust alternative to traditional transition modeling in complex, memory-heavy environments. By leveraging historical data directly as "maps" for the future, it avoids the dimensionality issues of expanded Markovian states. Future research directions include exploring more sophisticated distance metrics for scenario matching, implementing formal Bayesian belief updates, and extending the model to handle partial observability within the domain-level state $m$.
Summary updated