프로토-값 함수

응용 수학에서 proto-value 함수(PVF)는 자동으로 학습된 기본 함수로, 대략적인 과제별 가치 함수에 유용하며 전환 매트릭스의 힘을 압축적으로 표현한다.그들은 신용 할당 문제를 해결하기 위한 새로운 틀을 제공한다.이 프레임워크는 멀티스케일 스펙트럼과 다지관 학습 방법을 사용하여 마르코프 의사결정 과정(DP)과 학습 강화 문제를 해결하는 새로운 접근법을 도입한다.프로토-값 함수는 그래프 라플라시안 그래프를 사용하여 그래프의 스펙트럼 분석에 의해 생성된다.

프로토 가치 함수는 Sridhar Mahadevan에 의해 그의 논문 프로토 가치 함수에 의해 강화 학습의 맥락에서 처음 도입되었다. ICML 2005에서 개발 강화 학습.^[1]

동기

값 함수 근사치는 연속적인 상태 공간에 걸쳐 정의된 마르코프 의사결정 프로세스(DP)를 해결하는 데 중요한 요소다.좋은 함수 근사치는 보강 학습(RL) 에이전트가 그 가치를 명시적으로 저장하지 않고 경험한 상태의 가치를 정확하게 나타낼 수 있도록 한다.기준 함수를 사용한 선형 함수 근사치는 방사상 기준 함수, 다항식 상태 인코딩 및 CMAC와 같은 값 함수 근사치를 구성하는 일반적인 방법이다.그러나 이러한 기본 기능과 관련된 매개변수는 종종 상당한 영역별 수공학을 필요로 한다.^[2]프로토-값 함수는 문제 영역의 기초적인 다지관 구조를 고려하여 필요한 수공학을 해결하려고 시도한다.^[1]

개요

프로토-값 함수는 주어진 상태 공간에 대해 가능한 값 함수의 전체 공간을 포괄적으로 포괄하는 직무에 독립적인 글로벌 기본 함수다.^[1]그것들은 환경에 내재된 기하학적 제약을 포함한다.예를 들어 유클리드 거리에서 가까운 상태(벽 반대편의 상태 등)는 다지관 공간에서 멀리 떨어져 있을 수 있다.이러한 비선형성 문제에 대한 이전의 접근법에는 넓은 이론적 프레임워크가 결여되어 있었으며, 결과적으로 분리된 민주당원들의 맥락에서만 탐구되어 왔다.

프로토-값 함수는 값 함수 근사치의 문제를 그래프 또는 다지관의 실제 값 함수 근사치로 재구성하는 데서 발생한다.이는 학습된 기초의 적용 범위를 넓히고 표현과 정책을 동시에 학습하는 새로운 종류의 학습 알고리즘을 가능하게 한다.^[3]

그래프 Laplacian의 기본 함수

이 접근방식은 무작위 보행 운영자와 밀접하게 관련된 자기 적응(또는 대칭) 연산자인 그래프 라플라시안의 스펙트럼 분석에 의해 기본 기능을 구성한다.

For the sake of simplicity, assume that the underlying state space can be represented as an undirected unweighted graph ${\displaystyle G=(V,E)}$ The combinatorial Laplacian ${\displaystyle L}$ is defined as the operator ${\displaystyle L=D-A}$, where ${\displaystyle D}$ is a diagonal matrix call도 행렬과 $A{\displaystyle }$ ${\displaystyle A}$은 인접 행렬이다.^[1]

그래프에서 라플라스 연산자의 스펙트럼 분석은 방정식을 푸는 고유값과 고유특성을 찾는 것으로 구성된다.

${\displaystyle L\barphi _{\lambda }=\lambda \varphi _{\lambda }}$

where ${\displaystyle L}$ is the combinatorial Laplacian, ${\displaystyle \varphi _{\lambda }}$ is an eigenfunction associated with the eigenvalue ${\displaystyle \lambda }$. Here the term "eigenfunction" is used to denote what is traditionally referred to as eigenvector in linear algebra, because the Laplacian eigenv벡터는 당연히 각 정점을 실제 숫자에 매핑하는 함수로 볼 수 있다.^[3]

조합 라플라시안만이 그래프에서 선택할 수 있는 유일한 연산자가 아니다.기타 가능한 그래프 연산자에는 다음이 포함된다.

• ${\displaystyle \mathrm{정규화}}$된 라플라시안 $L{\displaystyle {}_{}}$ ${\displaystyle {\text{정규화}}_{}}$= I${\displaystyle }$- ${\displaystyle {\mathrm{D}}^{}}$- ${\displaystyle {}^{}}$/ 2 ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$ ${\$ 정규화$}=I-D^{-1/$2}}$AD^{-1/2}}$ ^[4]
• 무작위 $보행{\displaystyle }$P =${\displaystyle {}^{}}$ - ${\displaystyle {}^{}}$ ${\displaystyle {\mathrm{A}}^{}}$ ${\디스플레이 스타일$P=$D^{-1}A$}

이산 상태 공간에 대한 그래프 구성

유한 상태 공간의 경우 위에서 언급한$$ $그래프{\displaystyle }$ G ${\displaystyle G}$은 상태 간의 연결을 검사하여 간단하게 구성할 수 있다.$S{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$와 ${\displaystyle S_{}}$ j ${\$를 임의의 상태로 한다$$.그러면

${\displaystyle G_{i,j}={\begin{case}1&{{\text{{i}}}\{{j}\{0&\text{otherwise}}\case}}}}}}}$

주의할 점은 상태 공간이 유한하고 적당한 크기를 가져야 이것이 이루어질 수 있다는 것이다.

연속적 또는 큰 상태 공간에 대한 그래프 구성

연속 상태 공간 또는 단순하게 매우 큰 이산 상태 공간의 경우 상태 공간의 다지관에서 표본을 추출해야 한다.그런 다음 표본을 기준으로$$ 그래프 $G{\displaystyle }$ ${\displaystyle G}$을(를) 구성하십시오.여기서 고려해야 할 몇 가지 문제가 있다.^[4]

• 매니폴드 샘플링 방법
  • 무작위 걷기 또는 안내 탐색
• 두 표본이 연결되어야 하는지 확인하는 방법

적용

일단 PVF가 생성되면, 그것들은 전통적인 기능 근사치 프레임워크에 연결될 수 있다.그러한 방법 중 하나는 최소 제곱근법이다.

프로토-값 함수를 사용한 최소 제곱 근사치

Let ${\displaystyle \Phi _{G}=\left\{V_{1}^{G},\dots ,V_{k}^{G}\right\}}$ be the basis set of PVFs, where each ${\displaystyle V_{i}^{G}}$ is the eigenfunction defined over all states in the graph ${\displaystyle G}$. Let ${\displaystyle {\widehat$${V}^{\pi }}$은(는) $상태{\displaystyle {}_{}^{}}$ S ${\displaystyle {}_{}^{}}$ G${\displaystyle {}_{}^{}}$=${\displaystyle }${${\displaystyle {s\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle s_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\$의 부분 집합에 대해서만 알려진 대상 값 함수다$.$

그램 행렬 정의

${\displaystyle K_{G}=\왼쪽(\Phi _{m}^{G}\오른쪽)^{T}\Phi _{m}^{G}.}$

여기서 ${\displaystyle {Sm}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$은(는) PVF를 $S{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$에 있는 상태로의 구성 요소별 투영법이다$.$ 따라서 그램 매트릭스의 각 항목은 다음과 같다.

${\displaystyle K_{G}(i,j)=\sum _{k}V_{i}^{G}(k)V_{j}^{G}(k).}$

최소 제곱 오차를 최소화하는 계수는 방정식으로 설명된다.

${\displaystyle \alpha =K_{G}^{-1}\왼쪽(\Phi _{M}^{G}\오른쪽)^{{}}^{T}{\widehat{V}^{\pi }}$

비선형 최소 제곱 접근은 절대 계수가 가장 큰 k PVF를 사용하여 근사치를 계산할 수 있다.^[1]

참고 항목

• 강화학습
• 마르코프 의사결정 과정
• 기준함수
• 고유함수
• 라플라시안 행렬

참조