Q-러닝

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

Q-learning은 특정 상태에서 행동의 가치를 학습하기 위한 모델 없는 강화 학습 알고리즘입니다.환경 모델(따라서 "모델 프리")을 필요로 하지 않으며, 적응 없이 확률적 전환과 보상에 관한 문제를 처리할 수 있다.

모든 유한 마르코프 의사결정 프로세스(FMDP)에 대해 Q-러닝은 ^[1]현재 상태에서 시작하여 모든 연속 단계에 걸쳐 총 보상의 기대값을 최대화하는 의미에서 최적의 정책을 찾습니다.Q-learning은 무한 탐색 시간과 부분적으로 랜덤한 ^[1]정책이 주어진 주어진 주어진 FMDP에 대해 최적의 액션 선택 정책을 식별할 수 있습니다."Q"는 알고리즘이 계산하는 함수, 즉 주어진 ^[2]상태에서 수행된 동작에 대한 예상 보상입니다.

강화 학습

강화 학습에는 에이전트, 상태 $집합{\displaystyle }$ S$(\displaystyle$ S$)$ 및 상태별$동작{\displaystyle }$ 집합 A(\$displaystyle$ A$)$가 포함됩니다.$"A\displaystyle a\in$ A$"$ $액션$을 실행하면 에이전트는 스테이트에서 스테이트로 이행합니다.특정 상태에서 액션을 실행하면 에이전트에게 보상(숫자 점수)이 제공됩니다.

에이전트의 목표는 총 보상을 극대화하는 것입니다.미래 상태에서 얻을 수 있는 최대 보상을 현재 상태를 달성한 보상에 추가하여 잠재적인 미래 보상에 의해 현재의 행동에 효과적으로 영향을 미침으로써 이를 수행한다.이 잠재적 보상은 현재 상태에서 시작하는 모든 미래 단계의 보상에 대한 기대치의 가중치 합이다.

예를 들어, 보상은 탑승에 소요된 총 시간의 음수로 측정되는 열차 탑승 과정을 고려해 보십시오. (또는, 열차 탑승 비용은 탑승 시간과 동일합니다.)첫 번째 전략은 기차 문이 열리자 마자 문을 열고 들어가 자신을 위한 초기 대기 시간을 최소화하는 것입니다.하지만, 전철이 붐비면, 탑승하려고 할 때 사람들이 내리려고 다투기 때문에, 첫 번째 출입구 후에 천천히 들어갈 수 있습니다.총 탑승 시간 또는 비용은 다음과 같습니다.

• 0초 대기시간 + 15초 전투시간

다음 날 우연히 다른 사람이 먼저 출발할 때까지 기다리기로 합니다.이로 인해 처음에는 대기 시간이 길어집니다.그러나 출발하는 승객들과 싸우는 데 소비되는 시간은 더 적다.총 탑승 시간이 현재이기 때문에 전반적으로 이 경로는 전날보다 더 높은 보상을 받습니다.

• 5초 대기시간 + 0초 격투시간

탐구를 통해 초기(환자) 조치가 강제적인 전략보다 더 큰 비용(또는 부정적인 보상)을 발생시켰음에도 불구하고, 전체적인 비용이 낮기 때문에 더 보람 있는 전략이 드러난다.

알고리즘.

$향후의$$$을$$실행한 후$,$ 담당자는 몇개의 다음 스텝을 $결정$합니다.이 스텝의 가중치는 ${\displaystyle {\delta }^{}}$t \ $displaystyle$$$\ $gamma$^ { \ $Delta$ t$\}$ 로 계산됩니다.$여기$서 ${\$ \ $displaystyle$ \ $gamma$$$}(할인율)은${\displaystyle }$0 ~$(\displaystyle 0\$leq\$leq$1)의 수치이며 나중에 받은 값보다 높은 값을 반영합니다."좋은 출발"의 ue).${\displaystyle \gamma }$ may also be interpreted as the probability to succeed (or survive) at every step ${\displaystyle \Delta t}$.

따라서 알고리즘에는 상태-액션 조합의 품질을 계산하는 기능이 있습니다.

$displaystyle$$$$S\times$ A$\to$ \$mathbb {R}$$}$ 。

$학습$을 시작하기 전에 Q$(\displaystyle$ Q$)$는 임의의 고정값(프로그래머가 선택)으로 초기화됩니다.${\displaystyle {다음}_{}}$으로 t$\$$displaystyle$t마다 $에이전트$는 $액션$을 $선택$하고 보상 r\$displaystyle$ $r\_{\displaystyle {}_{}}$${t$을 준수하며 새로운 ${\displaystyle {상태}_{}}$ t${\displaystyle {}_{}}$$+$ $($$이전$ $상태{\displaystyle {}_{}}$ t$\$ $s_{t+1})$을 입력합니다(이전 상태 ${\displaystyle t_{}}$\displaystyle $s_{t}$와 선택한 액션에 따라 달라질 수 있음).$Q {$ $displaystyle$ Q$$}가$$ 갱신되었습니다.알고리즘의 핵심은 오래된 값과 새로운 정보의 가중 평균을 사용한 단순한 값 반복 업데이트로서의 벨만 방정식입니다.

${\displaystyle Q^{new}(s_{t},a_{t})\왼쪽 화살표 {Q(s_{t},a_{t}}_{\text {alpha}_{t})+\underbrace {\bigg}\cdot \brace {text}_{text}_r}_{t}_{\text{new value(일시적 차분 타깃)}}-\underbrace {Q(s_{t},a_{t}}_{\text{old value}}}}_^{\text{일시적 차분}}}}}$

${\displaystyle r_{}}$ ${\$$}$ 상태$$$t{\displaystyle {}_{}}$ {\$displaystyle s_{t$}}에서 $상태{\displaystyle {}_{}}$ ${\displaystyle t_{}}$+$$$displaystyle$$$$s_{t+1$로 이행했을 때 받는 보상입니다.$\alpha {\displaystyle }${\$displaystyle \alpha$는입니다

${\displaystyle Q^{}}$ ${\displaystyle n^{}}$ ${\displaystyle w^{}}$( ${\displaystyle s_{}}$t , ${\displaystyle a_{}}$t $){$ $displaystyle$ Q$^{new}(s_{t,a_{t})}$는 다음 3가지 요소의 합계입니다.

• ${\displaystyle }$( ${\displaystyle 1}$-${\displaystyle }$α )${\displaystyle Q}$ ( ${\displaystyle s_{}{}_{}{t}_{}}$ ,${\displaystyle {}_{}}$ )$$\ $displaystyle$( 1 - \$alpha$ )$Q$ ( s$_$ {$t$ , a$_$ { $t$} )$$: 학습 레이트에 의해 가중치가 부여되는 현재 값${\displaystyle .}$학습률 값이 1에 가까울수록 Q$(\displaystyle$ Q$)$의 변화가 빨라집니다.
• ${\displaystyle \alpha {}_{}}$ r ${\displaystyle t_{}}$\$displaystyle$\alpha $\r_{t$ : $상태{\displaystyle {}_{}}$ {{$displaystyle s_{t$}}$$ (학습률에 $따라{\displaystyle {}_{}}$ 가중치 부여됨)에서$$ {\$displaystyle$$r_{t$$$$}$$=r(s_{t})$를 취할 경우 얻을 $보상{\displaystyle {}_{}}$ ${\displaystyle r_{}}$ t ${\displaystyle {}_{}r}$ (${\displaystyle s_{}}$ t$)$
• ${\displaystyle \alpha }$ ${\displaystyle \underset{}{max}}$ ${\displaystyle \underset{}{max}}$ a${\displaystyle \underset{}{}}$ ( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$+${\displaystyle {}_{}{1}_{}}$ ,${\displaystyle a}$) { $displaystyle \alpha \gamma \max$ _${a}Q (s_{t+1$$})$$$} : $상태{\displaystyle {}_t}$ +$$ {$displaystyle s_{t+1$}$$(학습률과 할인율에 따라 가중치 부여됨)

알고리즘의 에피소드는 ${\displaystyle {상태}_{}}$ t${\displaystyle {}_{}}$+ $({$이 최종 상태 또는 단말 상태일 때 종료됩니다.그러나 Q-러닝은 (수렴 무한 급수의 속성으로 인해) 에피소드가 없는 작업에서도 학습할 수 있다.할인율이 1보다 작을 경우 문제가 무한 루프를 포함할 수 있더라도 액션 값은 유한합니다.

모든 최종 $상태{\displaystyle {}_{}}$$displaystyle$ $s_{f$$})$에 대해 Q($s$ f${\displaystyle {}_{}}$ $a)$는 업데이트되지 않지만 $상태{\displaystyle {}_{}}$ $(\$$f})$에 대해 관찰된 보상 값$r{\displaystyle }$(\$displaystyle$ r$)$로 설정됩니다.대부분의 경우 Q$(s$f,${\displaystyle }$a$)$는 $취득$할 수 $있습니다$.

변수의 영향

학습률

학습 속도 또는 단계 크기는 새로 획득한 정보가 오래된 정보를 어느 정도 덮어쓰는지 결정합니다.계수가 0인 경우 에이전트는 아무것도 학습하지 않고(사전 지식만 이용), 계수 1인 경우 에이전트는 최신 정보만 고려합니다(가능성을 탐색하기 위해 사전 지식 무시).완전 결정론적 환경에서는 ${\displaystyle {\alpha }_{}}$ t $=$ $(\displaystyle \alpha$ _${t}=1$)의 학습 속도가 최적이다.문제가 확률적인 경우, 알고리즘은 0으로 감소해야 하는 학습 속도에 대한 몇 가지 기술적 조건 하에서 수렴됩니다.실제에서는 $모든{\displaystyle }$t\$displaystyle$^[3]t에 대해 ${\displaystyle {\alpha }_{}}$ t $=$ ${\displaystyle 0}$.1$${\$displaystyle \alpha$ _${t$}=$0.1}$과 $같이{\displaystyle {}_{}}$ 일정한 학습률이 사용되는 경우가 많다.

할인율

할인율$${\(\$displaystyle$ \$gamma)$은 미래 보상의 중요성을 결정합니다$$.계수가 0인 경우 에이전트는 현재 보상(위의 업데이트$$에서는 r t {$displaystyle r_{$$t{\displaystyle {}_{}}$})만 고려함으로써 근시안적(또는 근시안적)이 되고, 1에 근접한 요인은 장기적인 높은 보상을 위해 노력하게 됩니다.할인 계수가 1을 충족하거나 초과하면 작용 값이 분산될 수 있습니다.${\displaystyle \mathrm{\gamma }}$ ${\displaystyle =}$1 {$displaystyle$ \$displaystyle =1}$의$$경우, 단말 상태가 없거나 에이전트가 단말 상태에 도달하지 않을 경우, 모든 환경 이력은 무한히 길어지고 할인되지 않은 추가 보상을 제공하는 유틸리티는 일반적으로 ^[4]무한하게 됩니다.할인 계수가 1보다 약간 낮더라도 가치 함수를 인공 ^[5]신경망으로 근사할 때 Q-함수 학습은 오류와 불안정성의 전파로 이어진다.이 경우, 낮은 할인율에서 시작하여 최종 가치를 향해 증가시키면 ^[6]학습 속도가 빨라집니다.

초기 조건(Q₀)

Q-learning은 반복 알고리즘이기 때문에 첫 번째 업데이트가 발생하기 전의 초기 조건을 암묵적으로 가정합니다."낙관적인 초기 조건"^[7]이라고도 하는 높은 초기 값은 탐색을 촉진할 수 있습니다. 즉, 어떤 액션이 선택되든 업데이트 규칙에 따라 다른 대안보다 낮은 값이 지정되므로 선택 확률이 높아집니다.첫 번째 $보상{\displaystyle }$ r$\displaystyle$r을$$ 사용하여 ^[8]초기 조건을 재설정할 수 있습니다.이 아이디어에 따르면 첫 번째 조치를 취했을 때 보상을 사용하여$$Q(\$displaystyle$ Q$)$의 값을 설정합니다.이것에 의해, 확정적인 보상이 있는 경우, 즉시 학습할 수 있습니다.초기 조건 재설정(RIC)을 포함하는 모델은 임의 초기 조건(AIC)^[8]을 가정하는 모델보다 참가자의 행동을 더 잘 예측할 것으로 예상된다.RIC는 반복적인 이진 선택 ^[8]실험에서 인간의 행동과 일치하는 것으로 보인다.

실행

Q-learning은 가장 간단한 방법으로 데이터를 테이블에 저장합니다.에이전트가 특정 상태를 방문하여 특정 액션을 수행할 가능성이 점점 낮아지기 때문에 이 접근 방식은 상태/액션 수가 증가함에 따라 흔들립니다.

함수 근사

Q-learning은 함수 ^[9]근사치와 결합할 수 있습니다.이를 통해 상태 공간이 연속적인 경우에도 알고리즘을 더 큰 문제에 적용할 수 있습니다.

한 가지 해결책은 (적용된) 인공 신경망을 함수 ^[10]근사기로 사용하는 것이다.또 다른 가능성은 퍼지 규칙 보간(FRI)을 통합하고 사람이 읽을 수 있는 지식 표현 형식이라는 장점이 있는 이산 Q 테이블 또는 ANN 대신 희박한 퍼지 규칙^[11] 베이스를 사용하는 것이다.알고리즘이 이전에 보이지 않았던 상태로 이전 경험을 일반화할 수 있기 때문에 함수 근사치는 유한 문제에서 학습 속도를 높일 수 있습니다.

양자화

상태/동작 공간을 줄이는 또 다른 기술은 가능한 값을 수량화합니다.손가락에 막대기 균형을 잡는 법을 배우는 예를 들어보자.특정 시점의 상태를 묘사하는 것은 공간에서의 손가락 위치, 속도, 막대기의 각도, 막대기의 각 속도를 포함한다.이것은 하나의 상태, 즉 4개의 값으로 인코딩된 1개의 상태의 스냅샷을 설명하는 4개의 요소 벡터를 생성합니다.문제는 무한히 많은 가능한 상태가 존재한다는 것이다.유효한 액션의 가능한 공간을 축소하기 위해 버킷에 여러 값을 할당할 수 있습니다.손가락의 시작 위치(-Infinity에서 Infinity까지)의 정확한 거리는 알 수 없지만, 오히려 멀리 있는지 여부(Near, Far)는 알 수 없습니다.

역사

Q-learning은 Chris Watkins에 의해 ^[12]1989년에 도입되었습니다.Watkins와 Peter Dayan은 ^[13]1992년에 수렴 증거를 제시했다.

왓킨스는 박사 논문의 제목인 "지연된 보상으로부터 배우는 것"을 말하고 있었다.8년 전인 1981년 보지노브스키의 크로스바 적응 어레이(CAA)^[14][15]에 의해 "지연 강화 학습"이라는 이름으로 동일한 문제가 해결되었다.메모리 $매트릭스{\displaystyle }$ W ${\displaystyle =ww}$ (${\displaystyle }$a ,${\displaystyle s}$ ) $、$ { $displaystyle$ W= \$w$ ($a$ , s$)\ }$는 8년 후의 Q-learning의 Q-table과 동일했습니다.아키텍처는 강화 학습에 "상태 평가"라는 용어를 도입했습니다.크로스바 학습 알고리즘은 각 반복에서 다음 계산을 수행합니다.

• 상태에서 액션 a를 실행한다.
• 결과 상태 s'를 수신한다.
• 컴퓨터 상태 $평가{\displaystyle }$v ( ${\displaystyle {}^{}}$ ${\displaystyle )}$) { $displaystyle$v ($s$ )$$;
• 크로스바 $값{\displaystyle {}^{}}$ w${\displaystyle {（}^{}}$ ${\displaystyle a}$,${\displaystyle s}$ ) $=$ (${\displaystyle a}$ ,${\displaystyle }$s ) +${\displaystyle v}$ ( ${\displaystyle {}^{}{)}^{}}$){ $display$ style w' ( a , s )=$w$( a ,$s$ )+v ( $s$)$$} 를 갱신합니다.

"2차 강화"라는 용어는 역전파를 통해 상태 값을 모델링하기 위해 동물 학습 이론에서 차용되었다. 결과 상황의 상태 값${\displaystyle }v{\displaystyle }$ ( $s$ ${\displaystyle )}$) {$displaystyle$v ($$s )}는$$ 이전에 직면한 상황에 역전파된다.CAA는 상태 값을 수직으로 계산하고 액션을 수평으로 계산합니다('크로스바').지연된 강화 학습을 보여주는 시연 그래프는 상태 평가 함수에 의해 계산된 상태(바람직한 상태, 바람직하지 않은 상태 및 중립 상태)를 포함했다.이 학습 시스템은 Q-learning ^[16]알고리즘의 선구자였습니다.

2014년 Google DeepMind는^[17] 전문가 수준의 Atari 2600 게임을 할 수 있는 "심층 강화 학습" 또는 "심층 Q-러닝"이라는 제목의 Q-러닝 애플리케이션을 딥러닝에 특허 등록했습니다.

변종

심층 Q-러닝

DeepMind 시스템은 수용 필드의 효과를 모방하기 위해 타일형 컨볼루션 필터 층이 있는 심층 컨볼루션 뉴럴 네트워크를 사용했습니다.강화학습은 뉴럴 네트워크 등의 비선형 함수 근사기를 사용하여 Q를 나타낼 때 불안정하거나 발산한다.이 불안정성은 관찰 시퀀스에 존재하는 상관관계, Q에 대한 작은 업데이트로 에이전트 및 데이터 배포 정책이 크게 변경될 수 있다는 사실 및 Q와 타깃 값 간의 상관관계에서 비롯됩니다.

이 기술은 생물학적으로 영감을 받은 메커니즘인 경험 리플레이를 사용했는데,^[2] 이 메커니즘은 진행하기 위해 가장 최근의 작용 대신 이전의 작용의 무작위 표본을 사용한다.이렇게 하면 관측 시퀀스에서 상관 관계가 제거되고 데이터 분포의 변화가 완화됩니다.반복 업데이트는 정기적으로만 업데이트되는 목표값으로 Q를 조정하여 ^[18]목표값과의 상관관계를 더욱 줄입니다.

더블 Q 러닝

Q-learning의 미래 최대 근사 액션 값은 현재 액션 선택 정책과 동일한 Q 함수를 사용하여 평가되므로 노이즈가 많은 환경에서는 Q-learning이 액션 값을 과대평가하여 학습이 느려질 수 있습니다.이를 수정하기 위해 Double Q-learning이라는 변종이 제안되었습니다.Double^[19] Q-learning은 정책 외 강화 학습 알고리즘으로 다음 액션 선택에 사용되는 정책과는 다른 정책이 가치 평가에 사용됩니다.

실제로 $({$ Q$^{A})$와 $({$ Q$^{B$의 두 가지 개별 가치 함수는 서로 대칭적인 방식으로 훈련됩니다.다음으로 더블 Q-learning 업데이트 순서는 다음과 같습니다.

$Q$$A}(s_{t},a_{t})$$=Q_{t$}^{A$}(s_{t},a_{t})+\alpha_{t}(s_{t}+\alpha Q_{t}^{B}\left(s_{t+$1},\$mathop {operatorname {max})_{A}^{A$}

$({displaystyle Q_{t+1}^{B}(s_{t,a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha_{t}(s_{t}+\alpha Q_{t}^{A}\left(s_{t+1},\mathop {operatorname {max})_{B}^{T}}$

이제 할인된 미래의 추정가치를 다른 정책을 사용하여 평가하여 과대평가 문제를 해결합니다.

이 알고리즘은 이후^{[clarification needed]} 2015년에 수정되어 DQN 알고리즘과 같이 딥 러닝과 결합되어 Double DQN이 생성되어 원래의 DQN ^[20]알고리즘을 능가한다.

다른이들

지연 Q-러닝은 온라인 Q-러닝 알고리즘의 대체 실장입니다.아마도 올바른(^[21]PAC) 학습이 있을 것입니다.

Gready GQ는 (선형) 함수 ^[22]근사치와 함께 사용하는 Q-러닝의 변형입니다.Gready GQ의 장점은 동작 값을 추정하기 위해 함수 근사치를 사용하더라도 컨버전스가 보장된다는 것입니다.

분산형 Q-러닝은 Q-러닝의 변종으로서 각 액션의 예상되는 리턴이 아닌 리턴의 분배를 모델화하려고 합니다.심층 신경망에 의한 추정을 용이하게 하고 위험에 민감한 ^[23]제어와 같은 대체 제어 방법을 가능하게 하는 것으로 관찰되었다.

제한 사항

표준 Q-learning 알고리즘($\displaystyle$ Q$)$ 테이블$$ 사용)은 개별 액션 및 상태 공간에만 적용됩니다.이러한 가치의 이산화는 비효율적인 학습으로 이어지는데, 이는 주로 차원성의 저주 때문이다.그러나 유선형 뉴럴 네트워크 ^[24]Q-러닝과 같이 이 문제를 해결하려는 Q-러닝의 적응이 있습니다.

「 」를 참조해 주세요.

• 강화 학습
• 시간차 학습
• 사사
• 죄수의 딜레마를 반복하다.
• 게임 이론

레퍼런스

외부 링크

• 왓킨스, C.J.C.H. (1989)지연된 보상을 통해 학습합니다.영국 케임브리지 대학 박사 학위 논문.
• Strehl, Li, Wiewiora, Langford, Littman(2006).PAC 모델 프리 강화 학습
• 강화 학습: 리처드 서튼과 앤드류 S. 바토의 소개, 온라인 교과서."6.5 Q-Learning: Off-Policy TD Control"을 참조하십시오.
• Piqle: 강화 학습을 위한 범용 Java 플랫폼
• Q-러닝을 이용해 미로를 통해 개미를 안내하는 '강화학습 메이즈' 시연
• Gerald Tesauro의 Q-learning 작업