Relationship-based access control (ReBAC) extends attribute- based access control (ABAC) to allow policies to be expressed in terms of chains of relationships between entities. ReBAC policy mining algorithms have potential to significantly reduce the cost of migration from legacy access control systems to ReBAC, by partially automating the development of a Re- BAC policy. This paper presents algorithms for mining ReBAC policies from information about entitlements together with information about entities. Our algorithms are designed to handle incomplete information about entitlements, typically obtained from operation logs, and noise (errors) in information about entitlements. We present two algorithms: a greedy search guided by heuristics, and an evolutionary algorithm. An evaluation of the algorithms on four sample policies and three large case studies demonstrates their effectiveness.