최대 점수를 기록한 서열?

Question

내가 n-states S = {s1, s2, s3, ..... sn}을 가지고 모든 전이, 즉 T- 행렬 f.e. s1 -> s5 = 0.3, s4 -> s3 = 0.7, ... 등.

상태 -x (s_x)부터 시작하여 가장 높은 점수를받은 시퀀스/경로를 선택하려면 어떤 알고리즘이나 절차를 사용해야합니까?

두 질문 :

1. 무한히 긴 경로에 내가 최선을 평균 가능한 상태로 선택할 수 있도록, 최선의 다음 상태를 선택?
2. 경로 길이 L이 주어지면 가장 높은 점수를 생성하는 상태 시퀀스를 선택 하시겠습니까?

저는 현재 강화 학습을 연구하고 있지만, 액션이나 정책이 없기 때문에 과도한 것처럼 보입니다. Value 함수와 같은 무언가를 사용할 수 있습니까?

무엇을 사용 하시겠습니까?

PS> 일부 시나리오에서는 T- 매트릭스가 시간이 지나면 변경 될 수 있습니다.

는

---

http://mnemstudio.org/path-finding-q-learning-tutorial.htm

은 Q-학습이 좋은 내기 것 같다. 내가 보는 유일한 차이점은 시간이 지남에 따라 Q 값을 저장하려면 T- 행렬을 변경하는 방법을 고려해야한다는 것입니다.

두 번째로 어려운 것은 최종 목표는 없지만 중간 점수 만 변경한다는 것입니다. 알고리즘 변경이 필요하지 않을 수도 있습니다. 간단히 말해 점수 변경에 수렴한다는 것입니다.

초기 단계는 L-steps 최적 경로 (즉, 매번 처음부터 Q를 다시 계산)를 수행 할 때마다 내 생각 이었지만, 입력 데이터에 따라 변경하는 Q 테이블을 유지하는 것을 선호합니다.

Answer 1

귀하의 옵션 1은 욕심이입니다. 이는 일반적으로 즉각적인 "최상의"옵션을 선택하는 접근 방식을 의미합니다. 문제는 탐욕스러운 선택이 미래에 최적의 선택을 제한 할 수 있다는 것입니다.

경로 길이 제한을 설정하지 않으면 최대 점수가 무한대입니다.

이제 질문은 다음과 같습니다. 주어진 경로 길이에 대해 가장 좋은 순서는 무엇입니까? 이것은 동적 프로그래밍과 같은 것들로 다항식 시간으로 풀 수 있습니다.

재귀 공식 (동적 프로그래밍 부분을 파악하는 데 사용할 수 있음)은 다음과 같이 나타낼 수 있습니다. 상태 x에서 시작하는 길이 L의 최적 경로를 계산하려면 모든 다른 상태 y를 살펴보십시오. 각각에 대해 T_xy + "상태 y에서 시작하는 길이 L-1의 최적 경로"를 계산하십시오.

분명히 어떤 상태 x에서 시작하는 길이 1의 최적 경로는 "다음 최상의 상태"가 될 것이므로 재귀에는 간단한 기본 경우가 있습니다.