Policy-based access control systems are crucial for secure information sharing in collaborative applications. However, policy management needs to be flexible in order to adapt to different environments and be able to support policy evolution. However, when dealing with large sets of evolving policies, it is critical that policies meet certain policy quality requirements. Policy sets must be complete, free of inconsistencies, and relevant. In this paper, we propose a framework to analyze policies to determine whether they meet such requirements. Our framework uses provenance techniques to collect comprehensive data about actions which were either triggered due to a network context or a user (i.e., a human or a device) action. The framework includes two approaches for policy analysis: structure-based and classification-based. For the structure-based approach, we designed tree structures to organize and assess the policy set efficiently. For the classification-based approach, we employed the classification techniques to learn the characteristics of policies and predict their quality. In addition, the framework includes the policy evolution module which mainly consists of recommendation and re-evaluation services for policy changes which both aim at fulfilling the policy quality requirements. The analysis framework has been implemented and experimental results from the prototype are reported.