problem1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/BitByBitAIGroup/Lab-Problem-1/blob/main/problem1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "\n",
        "class QuizMDP:\n",
        "    def __init__(self, rewards, probabilities):\n",
        "        # Rewards for each question\n",
        "        self.q_rewards = rewards\n",
        "        # Probabilities of answering a question correctly\n",
        "        self.q_probs = probabilities\n",
        "        # Total number of questions\n",
        "        self.num_questions = len(rewards)\n",
        "        # Total number of states (questions + end state)\n",
        "        self.num_states = self.num_questions + 1\n",
        "        # Starting state\n",
        "        self.start_state = 0\n",
        "        # End state\n",
        "        self.end_state = self.num_states - 1\n",
        "\n",
        "    # Get the probabilities of transitioning to the next state\n",
        "    def get_transition_probs(self, state, action):\n",
        "        if state == self.end_state:\n",
        "            # If already in the end state, stay there with probability 1\n",
        "            return [(self.end_state, 1.0)]\n",
        "        elif action == 1:\n",
        "            # If answering a question, transition to the next state with probability q_probs[state]\n",
        "            # or go to the end state with probability 1 - q_probs[state]\n",
        "            return [(state + 1, self.q_probs[state]), (self.end_state, 1 - self.q_probs[state])]\n",
        "        else:\n",
        "            # If passing, go directly to the end state with probability 1\n",
        "            return [(self.end_state, 1.0)]\n",
        "\n",
        "    # Get the rewards for transitioning to the next state\n",
        "    def get_rewards(self, state, action, next_state):\n",
        "        if next_state == self.end_state:\n",
        "            # If already in the end state, get no reward\n",
        "            return 0\n",
        "        elif action == 1:\n",
        "            # If answering a question, get the reward for the current state\n",
        "            return self.q_rewards[state]\n",
        "        else:\n",
        "            # If passing, get no reward\n",
        "            return 0\n",
        "\n",
        "# Use value iteration to find the optimal policy\n",
        "def find_optimal_policy(mdp, gamma=1.0, theta=1e-6):\n",
        "    # Initialize the value function to zero\n",
        "    value_function = np.zeros(mdp.num_states)\n",
        "\n",
        "    while True:\n",
        "        # Initialize the change in V to zero\n",
        "        max_change_in_value_function = 0\n",
        "\n",
        "        # Update the value function for each state\n",
        "        for state in range(mdp.num_states):\n",
        "            old_value_function = value_function[state]\n",
        "\n",
        "            # Get the maximum expected value for each action\n",
        "            expected_values_for_actions = []\n",
        "            for action in range(2):\n",
        "                expected_value_for_action = 0\n",
        "                for next_state, transition_probability in mdp.get_transition_probs(state, action):\n",
        "                    reward = mdp.get_rewards(state, action, next_state)\n",
        "                    expected_value_for_action += transition_probability * (reward + gamma * value_function[next_state])\n",
        "                expected_values_for_actions.append(expected_value_for_action)\n",
        "\n",
        "            value_function[state] = max(expected_values_for_actions)\n",
        "\n",
        "            # Update delta to keep track of the largest change in V\n",
        "            max_change_in_value_function = max(max_change_in_value_function, abs(old_value_function - value_function[state]))\n",
        "\n",
        "        # Check for convergence\n",
        "        if max_change_in_value_function < theta:\n",
        "            break\n",
        "\n",
        "    return value_function\n"
      ],
      "metadata": {
        "id": "3j6XjtL_qhwu"
      },
      "execution_count": 3,
      "outputs": []
    }
  ]
}