Design A Reinforcement Learning Algorithm ✓ Solved

Design A Reinforcement Learning Algorithm

Design A Reinforcement Learning Algorithm

Your task, put simply, is to design a reinforcement learning algorithm to teach the mouse how to find the food. The fundamental task involves a 100x100 grid where each cell can either contain a mouse or food. There is only one mouse in this grid, and an arbitrary number of food items scattered throughout. The mouse can sense the presence of food within a 3x3 matrix around it, representing its sense of smell, which considers the intensity of smell based on the proximity and quantity of nearby food. This sensory input forms the primary input for your reinforcement learning model. The mouse has a limited energy supply that gets replenished upon consuming food; if energy depletes completely, the mouse dies and the simulation ends. The mouse can move in four directions—North, South, East, and West—using the learned policy to reach and consume all food as efficiently as possible. The simulation is visualized via PyGame.

In addition to a reinforcement learning approach, you may also develop a trivial solution based purely on the scent's function as a distance-based heuristic. You are encouraged to compare the RL-based strategy to this simple heuristic to evaluate performance improvements. Each time step involves running a forward pass through your model, which outputs four probabilities corresponding to each of the four directions. These probabilities determine the mouse's movement decisions during the simulation.

Questions to Consider

  • Does the order of inputs matter for the reinforcement learning model? (e.g., inputting (N,S,E,W) versus (N,E,S,W))
  • Does the order of inputs impact a closed-form solution?
  • Would it be better for reinforcement learning to select the movement with the highest probability or to sample a movement randomly weighted by the probability distribution? Why?

Tasks

1. Write a Reward Function

Design a reward function that considers the current game state, previous frames of sensory input, food levels, and the number of food tiles consumed. The reward function could be simple, such as rewarding the number of food tiles found, or it could incorporate reward shaping by considering multiple frames of previous inputs to provide more frequent signals (e.g., reward when the mouse moves closer to food and penalize when it moves away).

Questions

  • What would constitute a sparse reward function in this scenario?
  • How could the reward function be improved to facilitate more efficient learning?

2. Develop a Model

Create a model that takes as input the sensory data: specifically, the 3x3 scent matrix around the mouse minus the center (which is always zero). It should output four probabilities corresponding to moving in the North, South, East, and West directions. Your implementation should handle when to backpropagate rewards based on the mouse's action and game state, and when to continue running the simulation.

Optional Extra Credit Tasks

  • Introduce a variable SCENT_RANGE that decreases the scent sensing range, and analyze how this impacts the reward function and model training.
  • Add a secondary sense, such as sight, with a variable VARIABLE_TERRAIN that assigns energy costs to different terrain tiles. Modify the reward function accordingly, considering energy expenditure and terrain difficulty.

Questions for Additional Variables

How does adding variables like SCENT_RANGE and VARIABLE_TERRAIN influence the formulation of the reward function? Describe potential adjustments to incentivize efficient navigation and energy usage under these new conditions.

Sample Paper For Above instruction

Introduction

The implementation of reinforcement learning (RL) algorithms to emulate intelligent navigation in agents, such as a mouse navigating in a grid environment, has gained significant importance in AI research. The challenge involves designing an RL framework that enables the mouse to efficiently locate, seek, and consume food within a constrained environment, simulating realistic sensory processing, decision-making, and energy management. This paper discusses the design of such an RL system, emphasizing reward functions, model architecture, algorithm considerations, and handling environmental variables.

Designing the Reward Function

The reward function in RL defines the incentives guiding an agent's behavior. For the mouse simulation, a balanced reward structure encourages efficient food search, minimizes energy expenditure, and sustains survival. A coarse reward function might grant positive signals upon successfully consuming food, thereby reinforcing seeking behavior. Conversely, sparse reward settings assign a reward only when food is eaten, making learning more challenging, especially in large environments.

Reward shaping techniques, such as providing incremental rewards when the mouse moves closer to food or penalizing actions that increase energy expenditure, facilitate more rapid learning. Incorporating multiple past frames allows the formulation of a distance-based reward that dynamically nudges the agent toward food, promoting exploration and exploitation balance.

Reward Function Formulation

A practical reward function should consider:

  • Positive reinforcement for food consumption (+10)
  • Small penalties for unnecessary movement or energy use (-1 per move)
  • Penalties for losing energy or for inactivity
  • Reward shaping based on proximity to food, e.g., a positive delta when the closest food decreases in distance

Mathematically, this can be formulated as:

Reward = (Number of food tiles consumed * reward per tile) 


- (Energy spent * penalty factor) 


+ proximity-based rewards

Designing the RL Model Architecture

The model receives as input the 3x3 scent matrix (excluding the center), flattened into an 8-element vector. A suitable architecture could be a feedforward neural network with multiple fully-connected layers, culminating in a softmax layer outputting four probabilities corresponding to movement directions. The model's output can be interpreted as probabilities; during execution, a stochastic policy (sampling from this distribution) enhances exploration, while the greedy approach (choosing the highest probability) can exploit learned policies.

Learning Strategy and Algorithm

Policy gradient methods, such as REINFORCE or actor-critic algorithms, are well-suited for this problem. These methods estimate gradients based on reward signals, updating the policy network iteratively to maximize expected rewards. Critical considerations include initializing the policy, handling exploration-exploitation trade-offs, and applying reward discounting over the sequence of actions to encourage quicker food collection.

In practice, experience replay buffers, epsilon-greedy policies, and reward normalization can improve stability and convergence speed.

Handling Environmental Variables

Introducing environmental variables such as SCENT_RANGE and VARIABLE_TERRAIN adds complexity and realism. For example, decreasing SCENT_RANGE limits the sensor's perceptual horizon, requiring the agent to rely more on local cues, demanding an adaptation in the reward function that penalizes energy waste in longer searches. Incorporating VARIABLE_TERRAIN involves assigning energy costs to different tiles, which can be integrated into the reward function as part of the negative reward for movement, thus incentivizing efficient paths and terrain-aware navigation.

Adjustments to reward signals include:

  • Penalizing moves over high-energy tiles more heavily
  • Rewarding the agent for reaching food quickly while minimizing energy expenditure
  • Balancing exploration with energy conservation, especially in heterogeneous terrains

Conclusion

Designing an effective RL algorithm for the mouse navigation problem requires carefully crafted reward functions, suitable model architectures, and consideration of environmental variable impacts. Both exploration and exploitation strategies must be tailored to balance immediate goals (finding food) and long-term survival, especially when the sensing capabilities and terrain costs vary. Through iterative training and hyperparameter tuning, a robust policy can be learned that significantly outperforms trivial heuristics, demonstrating the power of reinforcement learning in complex, dynamic environments.

References

  • Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press.
  • Mnih, V., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529–533.
  • Lillicrap, T. P., et al. (2016). Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971.
  • Konda, V. R., & Tsitsiklis, J. N. (2000). Actor-critic algorithms. SIAM Journal on Control and Optimization, 38(2), 643-666.
  • Morales, R., et al. (2018). Reinforcement learning in complex environments: a survey. IEEE Transactions on Neural Networks and Learning Systems.
  • Sutton, R. S., & Barto, A. G. (1998). Reinforcement Learning: An Introduction. Adaptive Computation and Machine Learning Series.
  • Silver, D., et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489.
  • Thrun, S. (1992). Efficient reinforcement learning using neural network functions and rollouts. Advances in Neural Information Processing Systems.
  • Zhang, H., et al. (2020). A survey on deep reinforcement learning. Neurocomputing.
  • Li, L., et al. (2017). Reinforcement learning with complex action spaces. Proceedings of the AAAI Conference on Artificial Intelligence.

Related Assignments