Minimax regret criterion (Savage criterion) — 새비지 기준

새비지 기준 (최소 후회 기준이라고도 함) — 불확실성 하에서의 의사결정 방법 중 하나입니다. 이 기준은 다양한 결과의 확률이 알려지지 않은 상황에서 적용되며, 최적이 아닌 결정을 내림으로써 발생하는 잠재적 손실을 최소화하는 것을 목표로 합니다.

일반적 특성

불확실성 조건에서는 각 전략 선택의 결과가 정확히 결정되지 않습니다. 가능한 대안을 평가하기 위해 발트 기준, 후르비츠 기준, 라플라스 기준, 새비지 기준 등 여러 기준이 사용됩니다. 새비지 기준은 최대 이익 달성이 아닌 최대 후회의 최소화(최적의 가능한 결과와 비교한 손실)를 지향합니다.

후회란 특정 결과에서 최적 전략이 선택되지 않았기 때문에 발생한 기회 손실을 나타내는 값입니다.

새비지 기준 적용 알고리즘

• 보수 행렬 구성: 행은 가능한 전략에, 열은 가능한 사건 결과에 해당하는 표를 작성합니다. 각 셀에는 특정 전략과 결과에서의 기대 결과가 기록됩니다.
• 후회 행렬(리스크 행렬) 구성: 각 결과(열)에 대해 최대 보수 값을 결정합니다. 그런 다음 각 셀에 대해 후회 값을 계산합니다:
• 각 전략에 대한 최대 후회 결정: 후회 행렬의 각 행에서 최대 값(해당 전략의 최악의 경우)을 선택합니다.
• 최적 전략 선택: 최대 후회가 최소인 전략을 선택합니다.

따라서 새비지 기준은 잘못된 결정으로 인한 가능한 손실을 최소화하는 원칙을 구현합니다.

수학적 공식화

다음이 주어진다고 가정합니다:

• $S=\{s_1,s_2,\dots ,s_m\}$ — 이용 가능한 전략(대안)의 집합.
• $\Theta =\{{\theta }_1,{\theta }_2,\dots ,{\theta }_n\}$ — 가능한 자연 상태의 집합.
• $u(s_i,{\theta }_j)$ — 전략 $s_i$를 선택하고 상태 ${\theta }_j$가 발생했을 때의 보수(유용성) 함수. 흔히 보수 행렬 $A=[a_{ij}]$로 표현되며, 여기서 $a_{ij}=u(s_i,{\theta }_j)$.

새비지 기준은 후회(regret) 또는 기회 손실의 개념에 기반합니다. 자연 상태 ${\theta }_j$에서 전략 $s_i$에 대한 후회 $r(s_i,{\theta }_j)$는 해당 자연 상태 ${\theta }_j$에서 얻을 수 있었던 최대 가능 보수(해당 상태에 최적인 전략이 선택되었을 경우)와 전략 $s_i$의 실제 보수 간의 차이로 정의됩니다.

새비지 기준 적용 알고리즘:

1. 후회 행렬(리스크 행렬) 계산:

   a) 각 자연 상태(보수 행렬의 각 열)에 대한 최대 보수 탐색:

   $u_j^{\ast }=\underset{k=1,\dots ,m}{max}u(s_k,{\theta }_j)=\underset{k=1,\dots ,m}{max}{a}_{kj}$

   이는 상태 ${\theta }_j$가 발생했을 때 최선의 가능한 결과입니다.

   b) 후회 행렬의 원소 계산 $R=[r_{ij}]$:**

   $r_{ij}=r(s_i,{\theta }_j)=u_j^{\ast }-u(s_i,{\theta }_j)=(\underset{k=1,\dots ,m}{max}{a}_{kj})-a_{ij}$

   원소 $r_{ij}$는 전략 $s_i$의 보수가 상태 ${\theta }_j$에서 최대 가능 보수보다 얼마나 작은지를 나타냅니다. 모든 원소 $r_{ij}\ge 0$.

1. 각 전략에 대한 최대 후회 탐색: 각 전략 $s_i$(후회 행렬 $R$의 각 행)에 대해 후회 관점에서 최악의 가능한 결과를 결정합니다:

   $r_i^{max}=\underset{j=1,\dots ,n}{max}{r}_{ij}=\underset{j=1,\dots ,n}{max}((\underset{k=1,\dots ,m}{max}{a}_{kj})-a_{ij})$

1. 최소 최대 후회를 가진 전략 선택(후회의 미니맥스 원칙): 발견된 최대 후회를 최소화하는 전략 $s_{\text{Savage}}^{\ast }$를 선택합니다:

   $s_{\text{Savage}}^{\ast }=\arg \underset{i=1,\dots ,m}{min}(r_i^{max})=\arg \underset{s_i\in S}{min}(\underset{{\theta }_j\in \Theta }{max}r(s_i,{\theta }_j))$

   또는 $r_{ij}$의 표현을 대입하면:

   $s_{\text{Savage}}^{\ast }=\arg \underset{i=1,\dots ,m}{min}\left(\underset{j=1,\dots ,n}{max}[(\underset{k=1,\dots ,m}{max}{a}_{kj})-a_{ij}]\right)$

새비지 기준을 사용할 때 달성되는 최대 후회의 최솟값은 다음과 같습니다: $V_{\text{Savage}}=\underset{i=1,\dots ,m}{min}(r_i^{max})=\underset{i=1,\dots ,m}{min}\left(\underset{j=1,\dots ,n}{max}{r}_{ij}\right)$

따라서 새비지 기준은 각 자연 상태에 대해 최선의 가능한 행동 대비 최소한의 손실을 보장하는 전략을 선택하는 것을 목표로 합니다.

수학적 공식화의 핵심 사항:

• 후회 $r_{ij}$의 정의: 이것이 핵심 개념입니다. 후회는 열 j에서의 최선의 결과와 현재 결과 a_{ij} 간의 차이로 계산됨을 보여주는 것이 중요합니다.
• 후회 행렬 $R$: 구성 방법이 명시되어 있습니다.
• $r_i^{max}$ 탐색: 후회 행렬의 각 행에서 최댓값을 찾는 과정이 제시됩니다.
• 미니맥스 원칙: 후회 $max$의 $\arg min$를 통한 전략 선택이 명확하게 공식화되어 있습니다.
• 사용 표기법: 게임 이론 및 의사결정 이론의 표준 표기법 (S, Θ, u, a_ij, r_ij, max, min, arg min).

장점과 단점

장점:

• 리스크 최소화를 지향합니다.
• 높은 불확실성 조건에서 특히 효과적입니다.

단점:

• 기대 이익을 무시하고 가능한 손실에만 집중합니다.
• 지나치게 보수적인 결정으로 이어질 수 있습니다.

의사결정 기준

• 후르비츠 기준
• 라플라스 기준
• 발트 기준