Currently the behavior doesn't match the documentation. Initially I thought that this can be solved by adding the support of path-like objects and backporting this up to 3.6. But os.readlink() on Windows doesn't not support also bytes paths, and never supported. This looks to me now more like a new feature. In 3.6 and 3.7 we can resolve this issue by just updating the documentation.

Bytes paths on Windows were deprecated before 3.6. Since implementing PEP 529, their should be supported on Windows if they are supported on other platforms. We shouldn't use an 8-bit API like CreateFileA, but instead decode bytes paths with UTF-8 and use a Unicode API (this should be implemented in path_converter()).