dev-self 님의 블로그

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리| *그리드 예제로 Monte-Carlo Method 코드로 구현하기A: 에이전트의 시작 위치 (1,4)G: 목표 지점 (4,1)회색 칸: 일반 상태 (이동 가능)환경 설명:상태 공간 (State Space):4x4 그리드로 총 16개의 상태.특수 상태: 시작점 A(1,4), 목표점 G(4,1).행동 공간 (Action Space):상(↑), 하(↓), 좌(←), 우(→) 4가지 방향.전이 모델 (Transition Model):에이전트는 선택한 행동 방향으로 확실히 이동 (확률적 불확실성 없음).예: (1,4)에서 "우" → (2,4)로 이동.벽 충돌 시 제자리 유지: 예) (1,4)에서 "좌" → (1,4) 유지.G(4,1..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|ε-greedy 벨만 연산자의 축소 연산자 증명 과정1. ε-greedy 벨만 연산자 정의ε-greedy 벨만 연산자 T_ε*(V)는 다음과 같이 정의된다:확률 (1-ε)로 최적 행동을 선택하는 부분확률 ε/|A|로 무작위 행동을 선택하는 부분이를 수식으로 표현하면:2. 두 가치 함수의 차이 계산두 가치 함수 V¹과 V²에 대해 T_ε*의 차이를 계산한다:3. 삼각 부등식 적용위 식을 삼각 부등식을 이용해 다음과 같이 분해한다:4. 최적 행동 부분 분석최적 행동을 선택하는 부분(첫 번째 항)에 대해:max 연산자의 성질에 의해 다음 부등식이 성립한다: 이를 적용하면:그리고 추가로: 5. 무작위 행동 부분 분석무작위로 행동을 ..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|ε-soft 정책의 필요성강화학습에서 에이전트는 환경과 상호작용하면서 보상을 최대화하는 정책을 학습한다. 하지만 순수하게 탐욕적인(greedy) 정책만 따르면 탐색-활용 딜레마(exploration-exploitation dilemma)에 직면한다:활용(Exploitation): 현재까지 알고 있는 최적의 행동만 선택탐색(Exploration): 새로운 행동을 시도하여 더 나은 전략 발견ε-soft 정책은 이 딜레마를 해결하기 위한 방법으로, 각 상태에서:최적 행동을 높은 확률(1-ε+ε/|A|)로 선택다른 모든 행동도 최소한의 확률(ε/|A|)로 선택 1. ε-soft Policy Improvementε-soft 정책은 모..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|Monte-Carlo Control>1. Policy Evaluation현재 정책 π에 대한 가치 함수 V를 계산하여 Vπ로 수렴시킴. Monte-Carlo Prediction을 사용하여 경험을 통해 Vπ를 추정2. Policy Evaluation계산된 가치 함수 V를 기반으로 탐욕적(greedy) 정책으로 개선.최적 정책 π∗과 최적 가치 함수 V∗로 수렴.3. Monte-Carlo Prediction의 한계와 해결책문제:경험하지 못한 상태 s또는 상태-행동 쌍 (s,a)에 대한 가치 함수를 계산할 수 없음.해결책 1: Exploring Start모든 (s,a)를 경험할 수 있도록 임의의 상태에서 시작.모든 (s,a)에 대..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.|질문| "MDP 모델을 알고 있는 경우에는 동적 프로그래밍 방식으로 정확한 값을 계산할 수 있지만, 모델을 모르는 경우에는 샘플링을 통해 값을 추정하는데 이럴 때는 어떻게 해야할까?"1. Monte-Carlo Prediction의 Value Function 계산여기서 Returns(s)는 상태 s에서의 샘플 반환값(return)들의 리스트이며, gt​는 시간 t부터 에피소드 끝까지의 할인된 보상 합계. 이 식은 시간 t에서의 리턴 값을 계산한다. 현재 시점 t부터 에피소드 종료 시점 T까지의 모든 보상에 감가율(discount factor) γ를 적용하여 합산한 값이다.Monte-Carlo 방법은 실제 환경에서 여러 에피소드를 생성하고,..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리||Monte-Carlo Method|1. 대수의 법칙- Random Variable의 정의:임의의 random variable 𝑥있다고 가정.- Random Variable의 표본:𝑋1,𝑋2,⋯ ,𝑋𝑛​은 random variable 𝑥의 𝑛개의 표본을 나타냄.- 표본 평균:표본 평균 𝑋ˉ𝑛은 다음과 같이 정의:- 대수의 법칙 (Law of Large Numbers):표본의 크기 𝑛이 무한대로 갈 때, 표본 평균 𝑋ˉ𝑛은 random variable의 기대값 𝐸[𝑋]로 수렴.- 표본 평균의 분산:표본의 크기 𝑛이 무한대로 갈 때, 표본 평균 𝑋ˉ𝑛​의 분산은 0으로 수렴:2. 분산의 성질상수 곱..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|Value Iteration 코드 연습>예제 환경 구성그리드 크기: 3x3 (가로 3칸, 세로 3칸)에이전트 시작 위치: (0,0) (좌측 상단)목표 위치: (2,2) (우측 하단)행동 공간: 4가지 방향 이동0: 상 (↑)1: 우 (→)2: 하 (↓)3: 좌 (←)전이 모델에이전트가 선택한 방향으로 80%의 확률로 이동미끄러짐 효과로 20%의 확률로 제자리에 머무름그리드 경계를 벗어나는 이동 시도 시 제자리에 머무름보상 체계목표(G)에 도달하면 +10 보상그 외 모든 이동에는 0 보상할인율(감마)γ = 0.9이 그리드 환경에서는 Value Iteration 알고리즘을 사용하여 에이전트가 시작 위치(A)에서 목표 위치(G)까..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|Value Iteration: convergence of value iteration 2>28일차에 이어서 수식을 정리한다1. 첫 번째 수식1. 부등식의미: T∗(V′(s))의 값이 하한 Ci와 상한 T∗(V′(s) 사이에 있음용도: T∗연산 결과의 범위를 제한하는 보조 정리2. 거리 비교 의미: 첫 번째 부등식: 자기 자신과의 차이는 Ci와의 차이보다 작음 (의미상 중복 또는 오타). 두 번째 부등식: γ∥V′−V2∥∞로 상한 설정.핵심: T∗의 출력 차이가 할인 계수 γ로 축소됨을 보임. 3. 최대 기대값 차이:2. 두 번째 수식1. 최적 행동 정의의미: v2를 기반으로 한 최적 행동 amax⁡2 선택2. Bellman..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|Value Iteration: convergence of value iteration>Value Iteration의 주요 공식Vk+1​(s)는 상태 s에서 k+1 반복에서의 가치 함수maxa​는 기대 가치를 최대화하는 행동을 찾는다는 의미p(s′∣s,a)는 상태 s에서 행동 a를 취했을 때 상태 s'로 전이될 확률r은 즉각적인 보상γ는 할인 인자Vk​(s′)는 이전 반복에서의 상태 s'에 대한 가치 함수간단한 3×3 그리드 월드 예제로 설명:에이전트는 상, 하, 좌, 우 네 방향으로 이동 가능에이전트가 벽에 부딪히면 제자리에 정지목표 상태(오른쪽 하단 모서리)에는 +1 보상위험 상태(중앙 오른쪽)에는 -1 보상다른 모든 전이..

*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다. |내용 정리|1. Value Iteration의 정의:Value Iteration은 Policy Iteration의 한 방법으로, Policy Evaluation을 1-step만 수행하고 즉시 Policy Improvement를 진행일반적인 Policy Iteration과 달리, Value Iteration은 Policy Evaluation이 완전히 수렴할 때까지 기다리지 않음2.  1-step Policy Evaluation:모든 상태 𝑠∈𝑆에 대해 계산현재 정책 𝜋 하에서 1번의 백업(backup)만으로 다음 가치 함수 𝑉𝑘+1를 업데이트일반적인 Policy Iteration에서는 이 단계를 수렴할 때까지 반복하지만, Val..