상담원이 연속적인 상태 순서를 따르지 않는 경우 문제를 MDP로 모델링하려면 어떻게해야합니까?
내 문제에서 에이전트는 연속적인 상태 순서를 따르지 않고 $\epsilon$-우선 순위 대기열에서 최상의 쌍 (상태, 작업)을 탐욕합니다. 좀 더 구체적으로 말하자면 에이전트가$s$ 사용 가능한 작업을 엽니 다. $\{ a_i \}$, 그런 다음 각각을 추정합니다. $(s,a)$쌍 (DQN과 회귀)하고 대기열에 저장합니다. 내 에이전트가 상태로 변경하려면$s'$, 사용 가능한 작업 중 하나를 따르는 대신 대기열에서 최상의 쌍을 선택합니다. $\{ a_i \}$ 의 $s$. 상태는 다른 상태와 부분적으로 다른 동작 집합을 가지고 있습니다.
그러나 이러한 방식으로 에이전트가 연속적인 상태 순서를 따르지 않는 경우 MDP를 어떻게 모델링 할 수 있습니까?
더 구체적으로, 몇 가지 시드 URL을 입력하는 집중 크롤러가 있습니다. 시드와 함께 가능한 한 많은 관련 URL을 출력하고 싶습니다. RL 프레임 워크를 다음과 같이 모델링합니다.
- 상태 : 웹 페이지,
- 액션 : 주 웹 페이지의 아웃 링크 URL,
- 보상 : 외부 소스에서 웹 페이지 콘텐츠가 관련이 있는지 알고 있습니다.
문제는 크롤링하는 동안 에이전트가 연속적인 상태 전환을 따라 계속 진행하면 크롤링 트랩이나 로컬 최적화에 빠질 수 있다는 것입니다. 이것이 크롤링에서 우선 순위 대기열이 중요하게 사용되는 이유입니다. 크롤링 에이전트는 더 이상 연속적인 상태 전환 순서를 따르지 않습니다. 각 상태-작업 쌍은 예상 작업 값과 함께 우선 순위 대기열에 추가됩니다. 매번 대기열의 모든 쌍 중에서 가장 유망한 상태-작업 쌍을 선택합니다. 각 URL 동작은 추출 된 주 웹 페이지를 고려하여 추정 할 수 있습니다.
답변
근본적으로 문제는이 설정에서 상태와 작업이 무엇인지 혼동하고 있다는 것입니다. 웹 페이지는 귀하의 상태가 아닙니다. 당신의 상태는 쌍 + 쌍 의 전체 우선 순위 대기열입니다 . 당신의 행동은 당신이 선택한 쌍입니다.(website-outlink)(new_website-outlink)
이제 이것은 가변 크기의 상태 공간과 가변 크기의 동작 공간 문제 설정입니다. 이를 처리하기 위해 (일반적으로) state==observation그럴 필요가 없다는 점에 주목하여 시작하십시오 . 그래서 당신의 관찰은 무엇입니까? 관찰은 다음 중 하나의 가변 크기 배치입니다.
(website-outlink)쌍 또는next_website(각각next_website은 해당 쌍에 의해 결정됨)
이 두 가지 관찰은 모두 잘 작동 할 수 있습니다. 둘 중 하나를 선택하는 것은 에이전트가 "열기 전에 열어야 할 링크"또는 "유의미한 링크 (열기 후)"를 알기를 원하는지 여부에 달려 있습니다.
우선 순위 대기열이 본질적으로하는 일은 다음과 같은 깔끔한 트릭을 추가하는 것입니다.
- 상태를 순서대로 유지하는 계산상의 복잡성을 저장합니다 (상태는가
website아니라의 목록 / 배치 임을 기억하십시오website-outlink). - 각 작업에 대한 Q- 값을 불필요하게 다시 계산하지 않습니다 (작업이에서 아웃 링크를
new_website선택하는 것이 아니라 대기열에서 사용 가능한 모든 선택 항목에서 아웃 링크를 선택하는 것임을 기억하십시오).
그러나 실제로 두 번째 저장을하려면 각 쌍의 Q 값을 저장하는 것이 중요합니다 !!!
마지막으로 주목해야 할 점은 Replay Buffer를 사용하는 시나리오 (DQN을 선택했을 가능성이 있음)에서는 RB에서 배우는 동안 우선 순위 대기열을 사용할 수 없다는 것입니다. 이유를 확인하고 학습 과정이 실제로 어떻게 보이는지 자세히 알아 보려면 Q- 값 업데이트가 여기 공식에 의해 제공된다는 점을 기억 하십시오 . 당신의 상태 s_t는 (준 순서 1 ) 쌍의 배치입니다. Q(s_t, a_t)에 DQN 회귀를 실행 단지 출력 만 (이 배치에서 최고의 웹 사이트 / 쌍의 가이 상태에서 어떤 조치가 취해 졌는지 일관성을 유지하기 위해 RB에 전환을 추가 할 때 최상의 선택을 나타내는 색인을 추가합니다. 그러나 최적의 미래 가치 추정치를 계산하려면 다음 상태에서 모든 단일 웹 사이트 / 쌍의 Q- 값 을 다시 계산 해야합니다 . RB에서 훈련 할 때는 우선 순위 대기열을 사용할 수 없습니다.
1 마지막 웹 사이트를 보는 동안 포함 된 모든 웹 사이트에 대해 우선 순위 대기열이 있지만 new_website-outlink지금 추가하는 모든 쌍이 아직 정렬되지 않았습니다. 여전히 에이전트를 실행해야하며 나머지 우선 순위 대기열과 함께 주문하여 다음 상태를 생성 할 수 있습니다 ( new_new_website-outink쌍이 있으므로 여전히 주문되지 않음 ).