RL: non-associative setting vs associative setting

1. Non-associative Setting (비연합적 설정)

가장 단순한 형태의 강화학습(RL).
Environment에서 상태(State)의 변화가 없음.

대표적으로 Multi-armed Bandit (MAB) 문제가 여기에 해당.

• 상태 ($S$):
  • 단일 state($|S|=1$)만 존재.
  • 어떤 action을 해도 state가 변하지 않음.
• 상태 전이(transition) 확률 ($P$):
  • state가 하나뿐이므로 다음 state로 전이될 확률이 항상 1: $P(s|s, a) = 1$).
• 정책 ($\pi$):
  • agent는 state를 고려할 필요 없음
  • 단순히 어떤 action($a$)이 가장 좋은지만 결정하면 충분
• 학습의 핵심:
  • 특정 상황(=state)과 action을 연결(Associate)할 필요가 없음.
  • 오직 보상을 극대화하는 *단 하나의 최적 action *을 찾는 것이 목표.

2. Associative Setting (연합적 설정)

흔히 말하는 Full Reinforcement Learning 에 해당.

State가 여러 개이고 행동에 따라 state가 변하는 환경.

• 상태 ($S$):
  • 여러 개의 구별되는 상태($|S|>1$)가 존재.
• 상태 전이 확률 ($P$):
  • agent의 action($a$)에 따라
  • 다음 상태($s'$)가 결정되는 환경의 법칙(=state transition probability)이 중요하게 작용($P(s'|s, a)$).
• Policy ($\pi$):
  • agent는 현재 상태 $s$를 확인하고,
  • 그 상황에 가장 적합한 행동 $a$를 선택해야 함($\pi(a|s)$).
• 학습의 핵심 (Associative Search):
  • agent는 "어떤 state에서 어떤 행동(Action)이 최선인가"를 서로 연결(Associate)하여 학습해야 함.
  • 상황에 따라 전략을 바꿔야 하는 '연합적 탐색' 과정.

3. 핵심 비교 요약

구분	Non-associative (MAB)	Associative (Full RL)
구분	Non-associative (MAB)	Associative (Full RL)
상태 공간 ($S$)	단일 상태 (상황이 바뀌지 않음)	다중 상태 (상황이 계속 바뀜)
상태 전이 ($P$)	고려 대상 아님 (정적임)	핵심 요소 (행동이 다음 상태를 결정)
정책 ($\pi$)	단순 행동 선택 (어떤 것을 할까?)	상태-행동 매핑 (이 상황에선 뭘 할까?)
연합(Association)	불필요	필수 (상태와 행동을 짝지어야 함)
비유	어느 식당 음식이 맛있는지 찾는 것	상황(배고픔, 주머니 사정)에 맞춰 식당을 고르는 것

4. Stationary / Non-stationary와의 관계

• Stationary (정상성):
  • 상태 전이 확률($P$)이나 보상 함수($R$) 같은 환경의 규칙이
  • 시간이 상관없이 일정.
• Non-stationary (비정상성):
  • 시간이 흐름에 따라
  • 환경의 규칙($P$ 또는 $R$) 자체가 변하는 상태.

Associative setting이면서 Non-stationary인 환경이 가장 어려운 난이도에 해당.

작성하신 훌륭한 요약 글의 흐름을 유지하면서, Q-table의 역할과 다른 핵심 개념들 간의 상관관계를 정리한 4절을 추가해 드립니다. 주요 용어는 학습의 편의를 위해 영어로 병기하였습니다.

---

5. Q-table과 주요 개념 간의 관계 (Relationship with Key Concepts)

RL에서 agent가 state와 action을 연합(associate)하여 최적의 policy를 세우기 위해 사용하는 가장 대표적인 도구가 바로 Q-table 임.

• 정의 (Definition):

  • 특정 State ($s$)에서 특정 Action ($a$)을 취했을 때,
  • 장기적으로 얻을 수 있는 기대 보상의 합(Expected Cumulative Reward),
  • 즉 가치(Q-value)를 기록한 table.

• Associative Setting에서의 Q-table:

  • Q-table은 state를 행(Row)으로, action을 열(Column)로 가짐.
  • agent는 이 Q-table을 채워나감으로써
  • "어떤 state($s$)에서 어떤 action($a$)을 매핑(Associate)해야 하는지"를 구체적인 수치로 저장.

• Policy ($\pi$)과의 관계:

  • Q-table은 policy 그 자체는 아님.
  • 단, policy가 결정을 내리기 위해 참조하는 가장 중요한 사전(Dictionary) 혹은 데이터베이스(Database) 라고 볼 수 있음.
  • agent는 Q-table을 보고 "이 state에선 이 action의 점수가 제일 높네?"라고 판단하여 행동을 결정.
    • 예: Exploration and Exploitation을 조절하는 $\epsilon$-greedy 정책

• 상태 전이 확률(Transition Probability, $P$) 및 보상(Reward, $R$)과의 관계:

  • Q-table은 환경의 법칙($P, R$)을 직접 저장하고 있지 않음.
  • 대신, 불확실한 환경 속에서 부딪히며 얻은 경험을 가치(Value)라는 하나의 숫자로 압축하여 저장.
  • 따라서 agent는 환경의 모델($P$)을 몰라도 Q-table만 있으면 최적의 결정을 내릴 수 있음(Model-free RL).

구분	상태 전이 확률 ($P$)	Q-table ($Q$)
구분	상태 전이 확률 ($P$)	Q-table ($Q$)
질문	무슨 일이 일어날까?	얼마나 좋을까?
데이터	확률 분포 (0~1 사이)	기대 보상의 총합 (숫자)
성격	원인 (Cause)	결과 (Effect)
MAB(Non-associative)의 경우	항상 1 (상태가 안 변하니까)	각 arm의 평균 보상값

• 정상성/비정상성(Stationary / Non-stationary)과의 관계:
  • 정상성(Stationary) 환경
    • Q-table의 값들은 학습이 반복됨에 따라
    • 점차 하나의 최적값으로 수렴(Convergence).
  • 비정상성(Non-stationary) 환경
    • 환경의 규칙($P, R$)이 변하므로,
    • 과거의 값에 매몰되지 않도록 고정된 단계 크기(Constant Step-size, $\alpha$)를 사용하여
    • Q-table을 끊임없이 추적 및 업데이트(Tracking and Updating)해야 함.