# Stochastic Shortest Path

Stochastic Shortest Path는 상태와 행동이 있고, 행동 결과가 확률적으로 다음 상태를 정하는 문제에서 terminal state까지의 기대 비용을 최소화하는 모델입니다. Markov Decision Process의 특수한 형태이지만, absorbing state와 hitting time이 중심이라 shortest path, Bellman equation, linear equation 관점이 함께 등장합니다.

## 문제 신호

| 문제 표현 | Stochastic Shortest Path 관점 |
| --- | --- |
| 목표 상태에 도달할 때까지 비용이 누적된다 | hitting cost |
| 행동마다 여러 다음 상태가 확률로 주어진다 | stochastic transition |
| 실패하면 같은 상태로 돌아온다 | geometric expected cost |
| terminal state의 value는 0이다 | absorbing boundary |
| 기대 이동 횟수나 기대 비용을 묻는다 | Bellman equation |

일반 shortest path와 다른 점은 edge 하나를 선택해도 다음 정점이 확정되지 않는다는 것입니다.

## Bellman 식

상태 `s`에서 행동 `a`를 고르면 비용 `c(s,a)`를 내고 확률 `P(s'|s,a)`로 다음 상태가 됩니다.

```text
V(goal) = 0
V(s) = min_a c(s,a) + sum P(s'|s,a) * V(s')
```

terminal에 도달하지 못하고 영원히 도는 policy가 있으면 기대 비용이 무한대가 될 수 있습니다. 문제에서 모든 policy가 proper인지, 또는 최소 정책만 proper이면 되는지 확인해야 합니다.

식부터 세우기 전에 무한 기대 비용을 어떻게 처리할지 먼저 정해야 합니다. 목표 상태에 도달할 수 없는 상태가 있거나, 음수 비용 순환을 이용해 기대 비용을 계속 낮출 수 있거나, proper policy 존재가 입력 조건으로 보장되지 않으면 Bellman 식을 썼다는 사실만으로 유한한 답이 보장되지 않습니다. 출력 형식에 `IMPOSSIBLE`, `INF`, 특정 sentinel이 있는지 먼저 확인하고 나서 value iteration이나 선형 방정식 풀이로 넘어갑니다.

## 작은 예시

상태 `A`에서 목표 `G`로 가는 행동이 하나 있다고 하겠습니다.

```text
성공 확률 0.7: G로 이동, 비용 1
실패 확률 0.3: A로 돌아옴, 비용 1
```

Bellman 식은 아래와 같습니다.

```text
V(A) = 1 + 0.7 * V(G) + 0.3 * V(A)
V(G) = 0
0.7 * V(A) = 1
V(A) = 1 / 0.7
```

확률적으로 실패해도 반복할 수 있기 때문에 기대 비용은 단순 1이 아니라 성공까지의 geometric 기대 횟수입니다.

## Value Iteration 골격

아래 코드는 모든 비용이 비음수이고 모든 정책이 proper인 유한 모델의 value iteration 예시입니다.

아래 예시는 모든 비목표 상태에 행동이 있고 모든 정책이 proper인 유한 모델로 제한합니다. proper 정책 하나의 존재와 비음수 비용만으로는 충분하지 않습니다. 예를 들어 비용 0 자기 반복과 비용 1 종료 행동이 있으면 0에서 시작한 반복이 종료 정책의 비용 1을 찾지 못합니다. 고정 반복 횟수는 오차 보장을 대신하지 않습니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;

struct Transition {
    int nextState = 0;
    double probability = 0.0;
};

struct Action {
    double cost = 0.0;
    vector<Transition> transitions;
};

vector<double> stochasticShortestPathValueIteration(
    const vector<vector<Action>>& actions,
    int goal,
    int iterations
) {
    int n = (int)actions.size();
    vector<double> value(n, 0.0);
    vector<double> nextValue(n, 0.0);

    for (int iter = 0; iter < iterations; ++iter) {
        for (int state = 0; state < n; ++state) {
            if (state == goal) {
                nextValue[state] = 0.0;
                continue;
            }
            double best = numeric_limits<double>::infinity();
            for (const Action& action : actions[state]) {
                double candidate = action.cost;
                for (const Transition& transition : action.transitions) {
                    candidate += transition.probability * value[transition.nextState];
                }
                best = min(best, candidate);
            }
            nextValue[state] = best;
        }
        value.swap(nextValue);
    }

    return value;
}
```

정확한 오차가 필요한 문제에서는 단순 반복 횟수를 감으로 정하면 안 됩니다. 수렴성 조건이나 linear equation 풀이를 검토해야 합니다.

## Linear Equation으로 푸는 경우

policy가 고정되어 있으면 min이 사라지고 선형 방정식이 됩니다.

```text
V(s) - sum P(s'|s,pi(s)) * V(s') = c(s,pi(s))
```

상태 수가 작고 policy가 고정되어 있거나, 가능한 policy를 따로 고를 수 있다면 Gaussian elimination이나 sparse linear solver로 기대 비용을 선형계로 구할 수 있습니다. 실수 소거에는 조건수와 반올림 오차가 남습니다.

## Deterministic Shortest Path와의 관계

전이가 항상 한 상태로만 간다면 식은 일반 shortest path와 비슷해집니다.

```text
V(s) = min_a cost(s,a) + V(next(s,a))
```

비음수 edge면 Dijkstra, DAG면 topological DP를 쓸 수 있습니다. stochastic case에서는 자기 자신으로 돌아오는 확률 때문에 단순한 정점 순서가 없어질 수 있습니다.

## Proper Policy 체크

| 상황 | 해석 |
| --- | --- |
| 목표에 도달할 확률이 1인 정책 존재 | finite optimum 후보 |
| 어떤 상태에서 목표로 갈 방법이 없음 | value는 무한대 |
| 음수 비용 cycle 가능 | 기대 비용이 아래로 발산할 수 있음 |
| 실패 시 제자리 확률이 큼 | 수렴이 느려질 수 있음 |

문제에서 "항상 언젠가 도착한다"는 조건이 없다면, 무한 기대 비용 상태를 어떻게 출력해야 하는지도 확인해야 합니다.