Markov quá trình ra quyết

Question

alt text http://img693.imageshack.us/img693/724/markov.png

Tôi là một chút nhầm lẫn về một số điểm ở đây:

1. có nghĩa là gì khi nói rằng nó sẽ thành công 70% thời gian ông cố gắng một định hoạt động? Nó có nghĩa là mỗi lần anh ta cố gắng thực hiện một hành động A, nó sẽ 70% thời gian thực hiện hành động đó và 30% kia thực hiện hành động dẫn đến cùng một trạng thái, hoặc chỉ là nó như thể anh ta luôn làm hành động A, nhưng chỉ 30% số lần anh ta không làm điều đó? Tôi hy vọng tôi đang làm cho bản thân mình rõ ràng: (
2. Làm thế nào để có thể có nhiều trạng thái liên tiếp với cùng một tiện ích? Theo lý thuyết thì tiện ích không phải lúc nào cũng giảm, bạn càng ở xa các tiểu bang có phần thưởng thì càng cao?
3. Hiểu biết chỉ những thông tin tôi đưa ra ở trên, là nó có thể suy ra những gì là yếu tố chiết khấu (gamma)? Nếu có, làm thế nào?
4. có thể tính toán thưởng cho các bang? Làm thế nào?

Answer 1

Có một mẫu để xử lý hầu hết các sự cố MDP, nhưng tôi nghĩ bạn có thể đã bỏ qua một số thông tin từ mô tả sự cố, rất có thể nó liên quan đến trạng thái bạn đang cố truy cập hoặc cách tập kết thúc (điều gì sẽ xảy ra nếu bạn chạy khỏi mép lưới). Tôi đã cố gắng hết sức để trả lời các câu hỏi của bạn, nhưng tôi đã thêm một mồi vào quá trình tôi sử dụng để xử lý các loại vấn đề này.

Tiện ích thứ nhất là một biện pháp khá trừu tượng về số tiền bạn muốn ở trong một trạng thái nhất định. Nó chắc chắn có thể có hai tiểu bang với tiện ích bình đẳng, ngay cả khi bạn đo lường tiện ích với heuristics đơn giản (Euclidean hoặc Manhattan khoảng cách). Trong trường hợp này, tôi giả định rằng giá trị tiện ích và phần thưởng có thể hoán đổi cho nhau.

Về lâu dài, mục tiêu trong các loại vấn đề này có xu hướng là, làm cách nào để tối đa hóa phần thưởng dự kiến ​​(dài hạn) của bạn? Tốc độ học tập, gamma, kiểm soát mức độ nhấn mạnh của bạn trên trạng thái hiện tại so với nơi bạn muốn kết thúc - hiệu quả bạn có thể nghĩ về gamma như phổ phổ biến, 'làm những điều mang lại lợi ích nhất cho tôi trong thời gian này ' ở mức cực đoan khác ' khám phá tất cả các tùy chọn của tôi và quay lại tùy chọn tốt nhất '. Sutton và Barto trong cuốn sách trên reinforcement learning có một số thực sự tốt đẹp explanations về cách thức hoạt động này.

---

Trước khi bắt đầu, hãy quay lại câu hỏi và đảm bảo rằng bạn có thể tự tin trả lời các câu hỏi sau.

1. Trạng thái là gì? Ở đây có bao nhiêu tiểu bang?
2. Hành động là gì? Có bao nhiêu hành động?
3. Nếu bạn bắt đầu ở trạng thái u và bạn áp dụng một hành động, xác suất đạt được trạng thái mới v là gì?

Vì vậy, câu trả lời cho câu hỏi?

1. Trạng thái là một vectơ (x, y). Lưới là 5 x 5, vì vậy có 25 trạng thái.
2. Có bốn hành động có thể, {E, N, S, W}
3. Xác suất thành công đạt được trạng thái liền kề sau khi áp dụng hành động thích hợp là 0,7, xác suất không di chuyển (ở cùng trạng thái là 0,3). Giả sử (0,0) là ô trên cùng bên trái và (4,4) là ô dưới cùng bên phải, bảng sau đây cho thấy một tập con nhỏ của tất cả các chuyển tiếp có thể có.

 
Start State Action   Final State Probability 
--------------------------------------------------- 
(0,0)   E    (0,0)   0.3 
(0,0)   E    (1,0)   0.7 
(0,0)   E    (2,0)   0 
... 
(0,0)   E    (0,1)   0 
... 
(0,0)   E    (4,4)   0 
(0,0)   N    (0,0)   0.3 
... 
(4,4)   W    (3,4)   0.7 
(4,4)   W    (4,4)   0.3 

Làm cách nào chúng tôi có thể kiểm tra xem điều này có hợp lý cho vấn đề này không?

1. Kiểm tra xem bảng có số lượng mục nhập phù hợp hay không. Trên một lưới 5 5 có 25 trạng thái và 4 hành động, vì vậy bảng nên có 100 mục nhập.
2. Kiểm tra để đảm bảo rằng đối với cặp khởi động/trạng thái, chỉ hai mục nhập có xác suất khác không xảy ra.

---

Chỉnh sửa. trả lời yêu cầu cho xác suất chuyển đổi thành trạng thái mục tiêu. Các ký hiệu dưới đây giả định

• v là trạng thái cuối cùng
• u là trạng thái nguồn
• một là hành động, nơi mà nó không được đề cập, nó ngụ ý rằng hành động được áp dụng không phù hợp.

 
P(v=(3,3) | u =(2,3), a=E) = 0.7 
P(v=(3,3) | u =(4,3), a=W) = 0.7 
P(v=(3,3) | u =(3,2), a=N) = 0.7 
P(v=(3,3) | u =(3,4), a=S) = 0.7 
P(v=(3,3) | u =(3,3)) = 0.3 

Answer 2

ad.1) có lẽ không phải là rô bốt có luôn luôn di chuyển - tức là 30% đó là "ah, giờ tôi nghỉ một chút" hoặc "không có sức mạnh để di chuyển chút nào".

Answer 3

tôi đã xây dựng vấn đề này là một quá trình Quyết định hữu hạn-Horizon Markov và giải quyết nó thông qua Chính sách Iteration. Ở bên phải của mỗi lần lặp lại, có một biểu diễn lưới mã hóa màu của các hành động được đề xuất cho mỗi trạng thái cũng như lưới/ma trận thưởng ban đầu.

Xem lại chính sách/chiến lược cuối cùng ở Giai đoạn 4. Liệu nó có đồng ý với trực giác của bạn không?