IntelligentCrowd: Mobile Crowdsensing via Multi-agent Reinforcement Learning

Yize Chen, Hao Wang

TL;DR

This paper introduces "IntelligentCrowd," a novel multi-agent reinforcement learning (MARL) algorithm that empowers individual mobile users in crowdsensing (MCS) to make optimal sensing decisions. By modeling user interactions and environmental uncertainties as a multi-agent Markov Decision Process, IntelligentCrowd helps users maximize their personal payoffs in real-time, even with limited information about others.

What Problem Does This Paper Address?

Mobile crowdsensing (MCS) relies on a large number of users with smart devices to collect data for various applications. While much research focuses on how platforms can incentivize participation and allocate tasks, this paper tackles a crucial gap: understanding and optimizing the decision-making process from the user's perspective. Users face significant uncertainties, including unpredictable sensing environments and the unknown strategies of other participants. These uncertainties make it difficult for individual users to determine their optimal sensing effort to maximize their own rewards while minimizing costs (like battery drain). Existing approaches often overlook these complex interactions and the user-centric view, leading to potentially suboptimal outcomes for participants.

Methods

The core of this paper is the development of the IntelligentCrowd algorithm, which uses a multi-agent reinforcement learning (MARL) approach. Specifically, it models the MCS system as a multi-agent Markov Decision Process (MDP). Each user (agent) makes decisions about their sensing effort based on local information (their own past sensing quality) and aims to maximize their discounted future payoffs.

IntelligentCrowd employs an actor-critic architecture for each agent.

  • Actor networks learn the policy for sensing effort, mapping observed states (past sensing quality) to actions (effort levels).
  • Critic networks estimate the value of these actions, helping to guide the actor's learning.

A key aspect is the centralized training with decentralized execution paradigm. During training, critic networks can leverage information from all agents to learn the complex interdependencies. However, during real-world execution, each agent's actor network operates independently, using only its local observations. This allows for distributed implementation without requiring constant communication between users. The algorithm also incorporates an experience replay buffer to store and learn from past interactions.

Datasets

The paper does not use pre-existing datasets for training or evaluation. Instead, it relies on simulated sensing environments to test the IntelligentCrowd algorithm. These simulated environments are designed to mimic various real-world scenarios, including:

  • Sine Dynamics: Periodic sensing signals with fixed amplitude and frequency.
  • Linear Dynamics: Periodic sensing signals with linear strength over time.
  • Markov Chain Dynamics: Finite state space Markov chains to represent temporal evolution of sensing quality.

The authors also introduce variations within these dynamics (different frequencies, amplitudes, transition matrices) and allow for negative sensed signals to simulate noisy or incorrect information, making the evaluation more challenging.

Key Insights and Ideas

  • User-centric optimization is crucial: Focusing on maximizing individual user payoffs, rather than just platform efficiency, can lead to better outcomes for participants.
  • MARL is well-suited for MCS: The complex, interactive, and uncertain nature of MCS makes MARL a powerful tool for learning optimal decentralized strategies.
  • Decentralized execution is feasible: The IntelligentCrowd's actor-critic architecture allows for training in a centralized manner but deployment in a distributed fashion, which is essential for practical MCS systems.
  • Historical context matters, but not indefinitely: The window length (K) of past observations significantly impacts learning. While longer windows generally improve performance, excessively long windows offer diminishing returns and increase computational cost.
  • Heterogeneous environments are challenging but manageable: The algorithm can learn effective strategies even when participants face different sensing dynamics, though convergence might take longer for more complex environments.

Key Results

  • Significant payoff improvement: IntelligentCrowd demonstrably improves users' payoffs compared to baseline approaches, especially in sequential MCS tasks under various sensing dynamics.
  • Stable learning: The algorithm shows stable learning behavior, with payoffs converging to a good level after a moderate number of training episodes.
  • Performance across dynamics: In simulations, participants using IntelligentCrowd achieved positive payoffs across Sine, Linear, and Markov chain dynamics, even when these dynamics were mixed among agents.
  • Comparison to MPC: The paper compares IntelligentCrowd to a Model Predictive Control (MPC) approach. IntelligentCrowd consistently outperformed MPC, achieving higher accumulated rewards and avoiding negative payoffs, particularly in mixed dynamics scenarios. MPC's reliance on local models and lack of coordination proved detrimental.
  • Scalability: The paper shows that the algorithm can scale to larger numbers of agents (e.g., 8 agents), with average rewards converging, though learning takes longer with more participants.

Limitations and Future Work

  • Problem Size Limitations: The current algorithm requires a number of actor-critic networks equal to the number of agents. This can become computationally prohibitive for very large-scale MCS systems.
  • Future Work: The authors suggest pre-processing and clustering steps to manage larger problem sizes.
  • Interaction with Platform Design: The current work focuses on user decision-making given an incentive mechanism.
  • Future Work: Exploring the interactions between the platform's mechanism design and the participants' decision-making is a promising direction.
  • Communication: While decentralized execution is achieved, explicit communication strategies between agents are not explored.
  • Future Work: Investigating how sharing representations or limited communication could further enhance performance is suggested.

Summary updated

Abstract

The prosperity of smart mobile devices has made mobile crowdsensing (MCS) a promising paradigm for completing complex sensing and computation tasks. In the past, great efforts have been made on the design of incentive mechanisms and task allocation strategies from MCS platform's perspective to motivate mobile users' participation. However, in practice, MCS participants face many uncertainties coming from their sensing environment as well as other participants' strategies, and how do they interact with each other and make sensing decisions is not well understood. In this paper, we take MCS participants' perspective to derive an online sensing policy to maximize their payoffs via MCS participation. Specifically, we model the interactions of mobile users and sensing environments as a multi-agent Markov decision process. Each participant cannot observe others' decisions, but needs to decide her effort level in sensing tasks only based on local information, e.g., its own record of sensed signals' quality. To cope with the stochastic sensing environment, we develop an intelligent crowdsensing algorithm IntelligentCrowd by leveraging the power of multi-agent reinforcement learning (MARL). Our algorithm leads to the optimal sensing policy for each user to maximize the expected payoff against stochastic sensing environments, and can be implemented at individual participant's level in a distributed fashion. Numerical simulations demonstrate that IntelligentCrowd significantly improves users' payoffs in sequential MCS tasks under various sensing dynamics.
BibTeX
@article{chen2018intelligentcrowd,
  author = {Yize Chen and Hao Wang},
  title = {{IntelligentCrowd: Mobile Crowdsensing via Multi-agent Reinforcement Learning}},
  journal = {IEEE Trans. Emerg. Top. Comput. Intell.},
  year = {2018},
  url = {https://openreview.net/forum?id=iGBRPN8WMx},
}
Figure