Структура данных для Марковского процесса принятия решений

Я реализовал алгоритм итерации значения для простого процесса принятия решения по методу Маркова Wikipedia в Python. Чтобы сохранить структуру (состояния, действия, переходы, награды) конкретного марковского процесса и перебрать его, я использовал следующие структуры данных:

  • словарь для состояний и действий, доступных для этих состояния:

    SA = { 'state A': {' action 1', 'action 2', ..}, ...}

  • словарь для вероятностей перехода:

    T = {('state A', 'action 1'): {'state B': probability}, ...}

    Словарь

  • для вознаграждений:

    R = {('state A', 'action 1'): {'state B': reward}, ...}.

Мой вопрос: правильно ли это? Каковы наиболее подходящие структуры данных (в Python) для MDP?

Ответы

Ответ 1

Независимо от того, подходит ли структура данных или нет, в основном зависит от того, что вы делаете с данными. Вы отмечаете, что хотите перебрать процесс, поэтому оптимизируйте свою структуру данных для этой цели.

Переходы в марковских процессах часто моделируются матричными умножениями. Вероятности перехода Pa(s1,s2) и вознаграждения Ra(s1,s2) могут быть описаны (потенциально разреженными) матрицами Pa и Ra, индексированными состояниями. Я думаю, что это будет иметь несколько преимуществ:

  • Если вы используете массивы numpy для этого, индексирование, вероятно, будет быстрее, чем со словарями.
  • Также состояние переходов может быть просто описано с помощью матричного умножения.
  • Моделирование процесса, например, с выбором колеса рулетки, будет выполняться быстрее и более четко, так как вам просто нужно выбрать соответствующий столбец матрицы перехода.

Ответ 2

Я реализовал Марковские процессы принятия решений на Python раньше и нашел следующий код полезным.

http://aima.cs.berkeley.edu/python/mdp.html

Этот код взят из "Искусственного интеллекта: современный подход" Стюарта Рассела и Питера Норвига.

Ответ 3

Существует реализация MDP с python под названием pymdptoolbox. Он разработан на основе реализации с Matlab под названием MDPToolbox. Оба стоит отметить.

В принципе, матрица перехода вероятности представляется как массив (A × S × S) и вознаграждается как матрица (S × A), где S и A представляют количество состояний и количество действий. В пакете также есть специальная обработка для разреженной матрицы.